💬 Discord
Sign In
NeetCode #482LC-212HardTriesBlind 75NC 150NC 250
← Back to All Problems

#482 · #212 · Word Search II(单词搜索 II)

📌 Problem Statement & Constraints

Given an m x n board of characters and a list of strings words, return all words that can be formed by sequentially adjacent cells (horizontally or vertically), without reusing a cell within a word. Constraints: 1 <= m, n <= 12, 1 <= words.length <= 3 * 10^4, word lengths up to 10.

💡 Core Algorithmic Approaches

  1. Insert all words into a trie so that shared prefixes are explored once.
  2. DFS from every cell, walking down the trie; a word is found when a node carries the end marker.
  3. Delete the end marker once a word is recorded, so duplicates are never added.
  4. Mark the current cell as visited (e.g. with a sentinel character) and restore it on backtrack.

💻 Benchmark Python3 Implementation

class Solution:
    def findWords(self, board: List[List[str]], words: List[str]) -> List[str]:
        # build the trie; the end marker stores the whole word
        root = {}
        for w in words:
            node = root
            for ch in w:
                node = node.setdefault(ch, {})
            node["#"] = w

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

        def dfs(r: int, c: int, node: dict) -> None:
            ch = board[r][c]
            if ch not in node:
                return
            nxt = node[ch]
            if "#" in nxt:                 # a complete word ends here
                res.append(nxt["#"])
                del nxt["#"]               # avoid recording it twice
            board[r][c] = "."              # mark visited (the board has no '.')
            for dr, dc in ((0, 1), (0, -1), (1, 0), (-1, 0)):
                nr, nc = r + dr, c + dc
                if 0 <= nr < m and 0 <= nc < n and board[nr][nc] != ".":
                    dfs(nr, nc, nxt)
            board[r][c] = ch               # restore on backtrack

        for i in range(m):
            for j in range(n):
                dfs(i, j, root)
        return res

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(m * n * 4^L) worst case, where L is the maximum word length -- but the trie prunes most branches.
💾 Space Complexity
O(total characters in words) for the trie plus O(L) recursion.

⚠️ Interview Pitfalls & Follow-ups

  • Searching each word independently with a plain DFS: it repeats the shared-prefix work, giving O(words * m * n * 4^L).
  • Forgetting to delete the end marker: a word appearing in several places would be recorded multiple times.
  • Not marking the cell as visited: a word could reuse a cell.
  • Forgetting to restore the cell: subsequent searches would see a corrupted board.
  • Using a separate visited set: it works but costs more than mutating the board in place.