Skip to content

212. Word Search II

On LeetCode ->

Problem

Return every word that can be traced in the character grid using horizontal or vertical moves without reusing a cell within the same word.

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

output = ["oath", "eat"]

Key trick

Store all words in a trie, then run DFS from each cell while following only trie prefixes; remove found words and exhausted branches to avoid repeated work.

Trap

  • Searching independently for every word repeats the same prefix searches and causes a time limit exceeded error.
  • A visited cell must be restored after each DFS path.
  • Finding one word must not stop the search because it may be a prefix of another word.
  • Result order is unspecified.

Why is it interesting?

It combines a trie with grid backtracking, turning many redundant word searches into one shared prefix search.

Python solution

class Solution:
    def findWords(self, board: list[list[str]], words: list[str]) -> list[str]:
        # Build a trie and store each complete word at its terminal node.
        trie = {}
        for word in words:
            node = trie
            for ch in word:
                node = node.setdefault(ch, {})
            node[""] = word

        m, n = len(board), len(board[0])
        res = []

        def dfs(r, c, parent):
            ch = board[r][c]
            node = parent.get(ch)
            if node is None:
                return

            # Popping prevents duplicate results from different paths.
            word = node.pop("", None)
            if word is not None:
                res.append(word)

            # Mark this cell as unavailable for the current path.
            board[r][c] = "#"

            for dr, dc in ((-1, 0), (1, 0), (0, -1), (0, 1)):
                nr, nc = r + dr, c + dc
                if 0 <= nr < m and 0 <= nc < n:
                    dfs(nr, nc, node)

            board[r][c] = ch

            # Remove branches that can no longer produce a word.
            if not node:
                parent.pop(ch)

        for r in range(m):
            for c in range(n):
                dfs(r, c, trie)

        return res

Let \(S\) be the total number of characters across all words, and let \(L\) be the maximum word length.

  • Worst-case time complexity: \(O\left(S + \text{rows} \cdot \text{cols} \cdot 4 \cdot 3^{L-1}\right)\)
  • Space complexity: \(O(S + L)\), excluding the result.

Comment on my solution

Your backtracking logic and cell restoration are correct, but the solution searches the entire board separately for every word.

Its worst-case time is approximately \(O(Wmn4 \cdot 3^{L-1})\), where \(W\) is the number of words. With up to \(3 \times 10^4\) words, repeated exploration of shared prefixes causes the timeout; a trie performs those shared searches only once.

class Solution:
    def findWords(self, board: list[list[str]], words: list[str]) -> list[str]:
        # board = [["o","a","a","n"],   words = ["oath","pea","eat","rain"]
        #          ["e","t","a","e"],
        #          ["i","h","k","r"],
        #          ["i","f","l","v"]]
        # -> ["eat","oath"]
        #
        # board = [["a","b"],   words = ["abcb"]
        #          ["c","d"]]
        # -> []

        rows, cols = len(board), len(board[0])
        result = []

        def dfs(r, c, i, word):
            if i == len(word):
                result.append(word)
                return True
            if r < 0 or r >= rows or c < 0 or c >= cols or board[r][c] != word[i]:
                return

            # mark cell
            ch = board[r][c]
            board[r][c] = "#"

            found = (
                dfs(r - 1, c, i + 1, word)
                or dfs(r + 1, c, i + 1, word)
                or dfs(r, c - 1, i + 1, word)
                or dfs(r, c + 1, i + 1, word)
            )

            board[r][c] = ch

            return found

        for word in words:
            for r in range(rows):
                found = False
                for c in range(cols):
                    if dfs(r, c, 0, word):
                        found = True
                        break
                if found:
                    break

        return result