Word Search II

Given a letter grid and a list of words, return every word that can be traced through adjacent cells without reusing a cell.

A way to picture it

It's a word-search puzzle with a whole list of words. Instead of hunting for each word separately, you carry one pocket dictionary shaped like a letter tree. As your finger slides across the grid, the dictionary tells you instantly whether any word could still continue that way.

How to approach it

Build a trie of the words, then DFS from every cell, moving through the trie in step. Abandon a path the moment the trie has no matching child.

Example

Input: {"board":[["o","a","a","n"],["e","t","a","e"],["i","h","k","r"],["i","f","l","v"]],"words":["oath","pea","eat","rain"]}. Output: ["eat","oath"].

Complexity: O(cells · 4 · 3^(L−1)) time and O(total letters) space. Each DFS branches to at most 3 unvisited neighbours; the trie prunes most paths early.

This page includes an animated walkthrough, Java and Python solutions, and a question to check your understanding.