Word Search II

hard trie backtracking grid

Problem

Given an m x n board of characters and a list of strings words, return all words on the board. Each word must be constructed from letters of sequentially adjacent cells, where adjacent cells are horizontally or vertically neighboring. The same letter cell may not be used more than once in a word.

Insert all words into a trie, with the word stored at its terminal node. DFS from each cell carrying a trie pointer; before exploring a neighbour, advance the trie pointer by that letter. As soon as the trie has no such child, prune. Whenever the current node holds a stored word, record it and clear the slot to avoid duplicates.

Inputgrid = [[o,a,a,n],[e,t,a,e],[i,h,k,r],[i,f,l,v]], words = [oath, pea, eat, rain]

Output[oath, eat]

"oath" follows (0,0)→(1,1)→(2,1)→(3,1); "eat" follows (1,3)→(1,2)→(0,2). "pea" and "rain" don't trace.

grid (rows separated by ';')

words

def find_words(grid, words):
    root = {}
    for w in words:
        n = root
        for c in w: n = n.setdefault(c, {})
        n["$"] = w
    out = []
    R, C = len(grid), len(grid[0])
    def dfs(r, c, n):
        ch = grid[r][c]
        if ch not in n: return
        nxt = n[ch]
        if "$" in nxt:
            out.append(nxt["$"]); del nxt["$"]
        grid[r][c] = "#"
        for dr, dc in ((-1,0),(1,0),(0,-1),(0,1)):
            nr, nc = r + dr, c + dc
            if 0 <= nr < R and 0 <= nc < C and grid[nr][nc] != "#":
                dfs(nr, nc, nxt)
        grid[r][c] = ch
    for r in range(R):
        for c in range(C): dfs(r, c, root)
    return out

function findWords(grid, words) {
  const root = {};
  for (const w of words) {
    let n = root;
    for (const c of w) n = n[c] || (n[c] = {});
    n.$ = w;
  }
  const out = [], R = grid.length, C = grid[0].length;
  function dfs(r, c, n) {
    const ch = grid[r][c];
    if (!n[ch]) return;
    const nx = n[ch];
    if (nx.$) { out.push(nx.$); delete nx.$; }
    grid[r][c] = "#";
    for (const [dr, dc] of [[-1,0],[1,0],[0,-1],[0,1]]) {
      const nr = r + dr, nc = c + dc;
      if (nr >= 0 && nr < R && nc >= 0 && nc < C && grid[nr][nc] !== "#") dfs(nr, nc, nx);
    }
    grid[r][c] = ch;
  }
  for (let r = 0; r < R; r++) for (let c = 0; c < C; c++) dfs(r, c, root);
  return out;
}

static class Node { Map<Character, Node> ch = new HashMap<>(); String word; }
List<String> out = new ArrayList<>();
char[][] g; int R, C;
public List<String> findWords(char[][] grid, String[] words) {
    g = grid; R = grid.length; C = grid[0].length;
    Node root = new Node();
    for (String w : words) {
        Node n = root;
        for (char c : w.toCharArray()) n = n.ch.computeIfAbsent(c, k -> new Node());
        n.word = w;
    }
    for (int r = 0; r < R; r++) for (int c = 0; c < C; c++) dfs(r, c, root);
    return out;
}
void dfs(int r, int c, Node n) {
    char ch = g[r][c];
    Node nx = n.ch.get(ch);
    if (nx == null) return;
    if (nx.word != null) { out.add(nx.word); nx.word = null; }
    g[r][c] = '#';
    int[][] D = {{-1,0},{1,0},{0,-1},{0,1}};
    for (int[] d : D) {
        int nr = r + d[0], nc = c + d[1];
        if (nr >= 0 && nr < R && nc >= 0 && nc < C && g[nr][nc] != '#') dfs(nr, nc, nx);
    }
    g[r][c] = ch;
}

struct Node { unordered_map<char, Node*> ch; string word; };
vector<string> out;
int R, C;
vector<vector<char>>* gp;
void dfs(int r, int c, Node* n) {
    char ch = (*gp)[r][c];
    if (!n->ch.count(ch)) return;
    Node* nx = n->ch[ch];
    if (!nx->word.empty()) { out.push_back(nx->word); nx->word.clear(); }
    (*gp)[r][c] = '#';
    int D[4][2] = {{-1,0},{1,0},{0,-1},{0,1}};
    for (auto& d : D) {
        int nr = r + d[0], nc = c + d[1];
        if (nr >= 0 && nr < R && nc >= 0 && nc < C && (*gp)[nr][nc] != '#') dfs(nr, nc, nx);
    }
    (*gp)[r][c] = ch;
}

Explanation

We want every dictionary word that can be traced through the grid by stepping to neighbouring cells. Searching each word separately is slow, so we put all words into one trie and explore the grid with DFS, carrying a trie pointer so we follow the grid and the trie in lockstep.

Each word is inserted into the trie with the full word saved at its final node (n["$"] = w). That stored word is how we know a complete match was traced.

From every cell we call dfs(r, c, node). If the cell's letter is not a child of node, we prune immediately — no word goes this way. Otherwise we descend the trie. If the new node holds a word, we record it and clear the slot (del nxt["$"]) to avoid duplicates.

To stop reusing a cell within one path, we temporarily mark it "#" before exploring the four neighbours, then restore it afterward (classic backtracking).

Example: word oath traces (0,0)o → (1,1)a → (2,1)t → (3,1)h. Sharing the trie across all words means dead-end letters get pruned early, which is why this beats checking words one by one.

Time: O(R · C · 4^L) Space: O(total word chars)