💬 Discord
Sign In
NeetCode #497LC-79MediumBacktrackingBlind 75NC 150NC 250
← Back to All Problems

#497 · #79 · Word Search(单词搜索)

📌 Problem Statement & Constraints

Given an m x n board of characters and a string word, return true if the word exists in the board via sequentially adjacent cells (horizontally or vertically), without reusing a cell. Constraints: 1 <= m, n <= 6, 1 <= word.length <= 15.

💡 Core Algorithmic Approaches

  1. DFS from every cell, matching the word character by character.
  2. Mark the current cell as visited before recursing, and restore it afterwards.
  3. The four directions are tried in order; any success short-circuits.
  4. Marking in place (with a sentinel) avoids allocating a visited set.

💻 Benchmark Python3 Implementation

class Solution:
    def exist(self, board: List[List[str]], word: str) -> bool:
        m, n = len(board), len(board[0])

        def dfs(r: int, c: int, i: int) -> bool:
            if i == len(word):
                return True                # the whole word was matched
            if not (0 <= r < m and 0 <= c < n) or board[r][c] != word[i]:
                return False
            ch = board[r][c]
            board[r][c] = "#"              # mark visited
            found = (dfs(r + 1, c, i + 1) or dfs(r - 1, c, i + 1)
                     or dfs(r, c + 1, i + 1) or dfs(r, c - 1, i + 1))
            board[r][c] = ch               # restore on backtrack
            return found

        for i in range(m):
            for j in range(n):
                if dfs(i, j, 0):
                    return True
        return False

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(m * n * 4^L) where L is the word length: each starting cell explores up to four branches per level.
💾 Space Complexity
O(L) for the recursion stack.

⚠️ Interview Pitfalls & Follow-ups

  • Checking the bounds after indexing: the bounds test must come first, before board[r][c].
  • Not restoring the cell after the DFS: later starting cells would see a corrupted board.
  • Using a visited set: workable but allocates; the in-place marker is cheaper. (Note: the marker must not collide with a real board character -- '#' is safe for letter-only boards.)
  • Returning True without short-circuiting the four directions: the or chain already does this.