Problem Statement

Given an m x n grid of characters board and a string word, return true if word exists in the grid.

The word can be constructed from letters of sequentially adjacent cells, where adjacent cells are horizontally or vertically neighboring. The same letter cell may not be used more than once.

Additional information

• m == board.length
• n = board[i].length
• 1 <= m, n <= 6
• 1 <= word.length <= 15
• board and word consists of only lowercase and uppercase English letters.

Example 1:

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

Output: true

Example 2:

Input: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "SEE"

Output: true

Example 3:

Input: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCB"

Output: false

Brute Force (DFS with Visited Set)

Intuition

To find the word, we can check every single cell on the board. If the character at the current cell matches the first letter of our word, we can launch a Depth-First Search (DFS) from that cell.

To ensure we don't reuse the exact same cell twice in our current path, we can maintain a visited set that holds the coordinates (r, c) of the cells we are currently standing on. As we explore up, down, left, and right, we add the new cell to the visited set. If the path turns out to be a dead end, we backtrack by removing the cell from the visited set.

Algorithm

1. Store the dimensions ROWS and COLS of the board.
2. Create a visited set to track the coordinates currently used in the path.
3. Define a recursive function dfs(r, c, i) where i is the current character index in word.
4. Base Cases:

• If i == len(word), we have successfully found the whole word. Return True.
• If r or c are out of bounds, or board[r][c] != word[i], or (r, c) is in visited, we hit a dead end. Return False.

5. Add (r, c) to visited.
6. Recursively call dfs on the 4 adjacent neighbors (up, down, left, right) looking for the next character i + 1. If any of them return True, return True.
7. Backtrack: Remove (r, c) from visited so it can be used in other potential paths. Return False.
8. Loop through every cell in the board and call dfs(r, c, 0). If any return True, return True. Otherwise, return False.

def exist(board: list[list[str]], word: str) -> bool:
    ROWS, COLS = len(board), len(board[0])
    visited = set()
    
    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 (r, c) in visited):
            return False
            
        visited.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))
               
        visited.remove((r, c))
        return res
        
    for r in range(ROWS):
        for c in range(COLS):
            if dfs(r, c, 0):
                return True
                
    return False

Time & Space Complexity

• Time complexity: O(M * N * 3^L)

• Reason: M * N is the total number of cells on the board. From each cell, we explore up to a length of L (the length of the word). We branch in 3 directions (excluding the cell we just came from).

• Space complexity: O(L)

• Reason: The visited set and the recursion stack will hold at most L elements at any given time, where L is the length of the target word.

In-Place Backtracking DFS - Optimal Space

Intuition

Maintaining an external visited set with tuples takes extra memory and hashing overhead. We can optimize the space and speed by modifying the board directly in-place!

When we visit a cell, we temporarily change its character to a special symbol (like "#"). This instantly prevents the DFS from visiting it again, acting just like our visited set. Once the DFS returns from exploring that path, we change the "#" back to its original character to restore the board for future searches.

Algorithm

1. Store the dimensions ROWS and COLS.
2. Define dfs(r, c, i).
3. Base Cases:

• If i == len(word), return True.
• If r or c are out of bounds, or board[r][c] != word[i], return False.

4. Temporarily store the current character: temp = board[r][c].
5. Mark the board cell as visited: board[r][c] = "#".
6. Explore the 4 neighbors. If any return True, return True.
7. Backtrack: Restore the cell to its original character: board[r][c] = temp.
8. Return False.
9. Loop through every cell to start the search.

def exist(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 
            board[r][c] != word[i]):
            return False
            
        # Temporarily mark the cell as visited
        temp = board[r][c]
        board[r][c] = "#"
        
        # Explore all 4 adjacent directions
        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))
                 
        # Backtrack by restoring the original character
        board[r][c] = temp
        
        return found
        
    # Start DFS from every cell
    for r in range(ROWS):
        for c in range(COLS):
            if dfs(r, c, 0):
                return True
                
    return False

Time & Space Complexity

• Time complexity: O(M * N * 3^L)

• Reason: The time complexity remains mathematically the same, but the constant factors are much lower because we avoid hashing overhead from using a set.

• Space complexity: O(L)

• Reason: We eliminated the O(L) space previously required by the visited set. The only extra space used is strictly the O(L) required by the recursion stack.