Here is solutions for Word Search.

1. Understand the problem

• You are given:

  • A 2D grid board of characters.

  • A string word.

• You must determine whether the word exists in the grid.

• Rules:

  • The word must be constructed from sequentially adjacent cells.

  • Adjacent means up, down, left, right (no diagonals).

  • The same cell cannot be used more than once in a single word path.

2. Clarify constraints, asks 4 - 5 questions including edge cases.

1. Board size limits?

Typical constraints:

• 1 ≤ rows, cols ≤ 200

• 1 ≤ word.length ≤ 10^4

1. Can the word be longer than total cells?

• If len(word) > rows * cols → return False immediately.

1. Can letters repeat in the word and board?

• Yes. Repetition is allowed, but the same cell cannot be reused.

1. What if the board or word is empty?

• Empty word → always True.

• Empty board → always False unless word is empty.

1. Movement constraints?

• Only 4 directions (no diagonal).

• No wrap-around.

3. Explore examples.

1. Example 1:

Board:
A B C E
S F C S
A D E E

Word = "ABCCED"
Output = True

• Valid path: A → B → C → C → E → D

1. Example 2:

Word = "SEE"
Output = True

1. Example 3:

board = [["A"]]
word = "A"   → True
word = "B"   → False

4. Brainstorm 2 - 3 solutions, naive solution first and optimize later. Explain the key idea of each solution.

4.1. Solution 1: Brute Force + Backtracking (Naive DFS) - Time O(M * N * 4^L), Space: O(L)

• Idea:

  • Start DFS from every cell that matches word[0].

  • Try all 4 directions recursively.

  • Mark visited cells so they are not reused.

  • Backtrack after exploration.

• Time: O(M * N * 4^L)

• Space: O(L)

4.2. Solution 2: Optimized DFS with In-Place Board Modification - Time O(M * N * 4^L), Space: O(L)

Idea:

• Using board[r][c] = ‘#’ to store the visited space.

Instead of using a separate visited matrix:

- Temporarily modify board[r][c] = '#'

- Restore it after backtracking.

Why better?

- Saves memory from using visited.

- Still same worst-case time but faster in practice.

4.3. Solution 3: Pruning with Character Frequency (Pre-Check Optimization)

Before DFS:

• Count frequency of each character in board.

• Count frequency in word.

If word needs more of any character → return False.

• This avoids expensive DFS when impossible.

5. Implement solutions.

5.1. Solution 1: Naive Backtracking with Path - Time O(M * N * 4^L), Space: O(L)

• Idea: Using path as visited array, Space O(L).

class Solution:
    def exist(self, board: List[List[str]], word: str) -> bool:
        ROWS, COLS = len(board), len(board[0])
        path = set()

        def dfs(r, c, i):
            if i == len(word):
                return True

            if (min(r, c) < 0 or
                r >= ROWS or c >= COLS or
                word[i] != board[r][c] or
                (r, c) in path):
                return False

            path.add((r, c))
            res = (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))
            path.remove((r, c))
            return res

        for r in range(ROWS):
            for c in range(COLS):
                if dfs(r, c, 0):
                    return True
        return False

We have visited array, space O(L).

• Time: O(M * N * 4^L)

• Space: O(L)

5.2. Solution 2: Backtracking with Visited - Time O(M * N * 4^L), Space: O(L)

Idea:

• Same idea but used visited array arr[r][c]

class Solution:
    def exist(self, board: List[List[str]], word: str) -> bool:
        ROWS, COLS = len(board), len(board[0])
        visited = [[False for _ in range(COLS)] for _ in range(ROWS)]

        def dfs(r, c, i):
            if i == len(word):
                return True
            if (r < 0 or c < 0 or r >= ROWS or c >= COLS or
                word[i] != board[r][c] or visited[r][c]):
                return False

            visited[r][c] = True
            res = (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))
            visited[r][c] = False
            return res

        for r in range(ROWS):
            for c in range(COLS):
                if dfs(r, c, 0):
                    return True
        return False

• Time: O(M * N * 4^L)

• Space: O(L)

5.3. Backtracking In-place marking - Time O(M * N * 4^L), Space: O(L)

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

        def dfs(r, c, i):
            if i == len(word):
                return True
            if (r < 0 or c < 0 or r >= ROWS or c >= COLS or
                word[i] != board[r][c] or board[r][c] == '#'):
                return False

            board[r][c] = '#'
            res = (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] = word[i]
            return res

        for r in range(ROWS):
            for c in range(COLS):
                if dfs(r, c, 0):
                    return True
        return False

• Time: O(M * N * 4^L)

• Space: O(L) recursion stack.

6. Dry run testcases.

board = [
  ["A","B","C","E"],
  ["S","F","C","S"],
  ["A","D","E","E"]
]
word = "ABCCED"