The problem
Given an m × n grid of letters, board, and a list of words, return every word that can be traced on the board, in any order.
A word is traced by moving between cells that touch horizontally or vertically, one letter per cell, using no cell twice in the same word.
Examples
- 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"]
- Input
board = [["a", "b"], ["c", "d"]], words = ["abcb"]
- Output
[]
Constraints
- 1 ≤ m, n ≤ 12
- 1 ≤ words.length ≤ 3 × 10⁴
- 1 ≤ words[i].length ≤ 10
- Only lowercase letters; the words are all different.
The idea
Searching the board once per word repeats the same walks thousands of times. Put all the words in one trie instead, and walk the board once: from each cell, a depth-first search follows the letters as long as the path spelled so far is a path in the trie.
When the walk reaches a node where a word ends, that word is found; remove it from the node so it is reported once. A cell is marked while it is on the current path, so it is not reused. And once a trie branch has no words left below it, cut it off — later walks stop there at once.
- Time
- O(m · n · 4 · 3ᴸ⁻¹) — each start, then at most 3 new directions a step, L the longest word
- Space
- O(total letters in words) — the trie
Solution · every language run against every case
class Solution: def findWords(self, board: List[List[str]], words: List[str]) -> List[str]: # One trie of all the words; a node keeps the word that ends there. root = {} for w in words: node = root for c in w: node = node.setdefault(c, {}) node["$"] = w rows, cols = len(board), len(board[0]) found = [] def dfs(r, c, parent): ch = board[r][c] node = parent[ch] if "$" in node: found.append(node.pop("$")) # take it once board[r][c] = "#" # in use on this path for nr, nc in ((r + 1, c), (r - 1, c), (r, c + 1), (r, c - 1)): if 0 <= nr < rows and 0 <= nc < cols and board[nr][nc] in node: dfs(nr, nc, node) board[r][c] = ch if not node: # nothing left to find below: prune the branch del parent[ch] for r in range(rows): for c in range(cols): if board[r][c] in root: dfs(r, c, root) return found