Word Search

Grid

Word Progress

Phase

Current Cell

Matched

Cells Explored

DFS Path

Empty

Click "Step" or "Play" to start the visualization

Default

Scanning

DFS Path

Current

Found

Backtrack

Python Code

                def exist(board, word):
            
                    for i in range(rows):
            
                        for j in range(cols):
            
                            if dfs(i, j, 0): return True
            
                    return False
            
                def dfs(r, c, k):
            
                    if k == len(word): return True
            
                    if out_of_bounds or board[r][c] != word[k]:
            
                        return False
            
                    board[r][c] = '#' # mark visited
            
                    found = dfs(r±1,c,k+1) or dfs(r,c±1,k+1)
            
                    board[r][c] = word[k] # restore
            
                    return found

Complexity Analysis

Time Complexity O(N·M·4^L) Space Complexity O(L)

Time Complexity: O(N · M · 4^L)

Breakdown

N × M cells as potential starting positions
From each starting cell, DFS explores up to 4 directions at each level
DFS depth is at most L (word length), giving 4^L branches
In practice, visited marking prunes most branches to 3 directions

T(N, M, L) = N × M × 4^L

Mathematical Intuition

The outer loop tries every cell as a potential word start. From each cell, the DFS branches into at most 4 directions at each character position. The exponential factor 4^L dominates, but in practice the search tree is heavily pruned by character mismatches and visited-cell checks, making the average case much faster.

Key Insight

Backtracking is essential: by restoring cells after exploration, the algorithm allows different starting positions to reuse the same cells in different paths. This correctness guarantee comes at the cost of potentially re-exploring cells across different starting points.

Space Complexity: O(L)

Breakdown

Recursion stack depth: at most L (word length)
In-place marking with '#' avoids a separate visited array
No additional data structures needed beyond the call stack

S(L) = O(L) for recursion depth

Mathematical Intuition

The algorithm modifies the board in-place to mark visited cells, restoring them on backtrack. This means no separate visited set is needed. The only space cost is the recursion stack, which goes at most L levels deep (one level per character in the word).

Key Insight

In-place marking is a classic space optimization for grid DFS. By temporarily mutating the input (board[r][c] = '#'), we get O(1) visited tracking per cell. The restore step (board[r][c] = word[k]) ensures the board is unchanged after the function returns.

Phase

Current Cell

Matched

Cells Explored

Time Complexity: O(N · M · 4L)

Space Complexity: O(L)

Time Complexity: O(N · M · 4^L)