Word Search, Boggle Solver, and Word Ladder: Grid + String Graph Problems

These three problems combine graph traversal with string processing. Word search uses DFS + backtracking on a grid. Boggle extends it to find multiple words using a Trie. Word ladder treats each word as a graph node and uses BFS for shortest transformation. Despite their differences, all three model relationships between characters or strings as graphs.

Word Search (LeetCode 79)

Given a 2D grid of characters and a target word, determine if the word exists in the grid. You can move up, down, left, right, and each cell can only be used once per word.

Core Idea

Start DFS from every cell that matches the first character. At each step, check if the current cell matches the expected character. If so, mark it visited and try all 4 neighbors for the next character. Backtrack (unmark) when returning.

def exist(board: list[list[str]], word: str) -> bool:
    """
    LeetCode 79: Word Search using DFS + backtracking.
    """
    rows, cols = len(board), len(board[0])
    
    def dfs(r: int, c: int, idx: int) -> bool:
        # All characters matched
        if idx == len(word):
            return True
        
        # Bounds check, character match, and visited check
        if (r < 0 or r >= rows or c < 0 or c >= cols or
            board[r][c] != word[idx]):
            return False
        
        # Mark as visited by replacing with special char
        temp = board[r][c]
        board[r][c] = '#'
        
        # Try all 4 directions
        found = (dfs(r+1, c, idx+1) or dfs(r-1, c, idx+1) or
                 dfs(r, c+1, idx+1) or dfs(r, c-1, idx+1))
        
        # Backtrack: restore original character
        board[r][c] = temp
        return found
    
    for r in range(rows):
        for c in range(cols):
            if board[r][c] == word[0] and dfs(r, c, 0):
                return True
    
    return False

Optimization: Character Frequency Pruning

Before starting the search, check if the grid even contains all characters needed.

from collections import Counter

def exist_optimized(board: list[list[str]], word: str) -> bool:
    """Optimized word search with frequency pruning."""
    rows, cols = len(board), len(board[0])
    
    # Frequency check: does the board have enough of each character?
    board_count = Counter()
    for row in board:
        board_count.update(row)
    
    word_count = Counter(word)
    for char, count in word_count.items():
        if board_count[char] < count:
            return False
    
    # Optimization: if the last character is rarer, search in reverse
    if board_count[word[0]] > board_count[word[-1]]:
        word = word[::-1]
    
    def dfs(r, c, idx):
        if idx == len(word):
            return True
        if (r < 0 or r >= rows or c < 0 or c >= cols or
            board[r][c] != word[idx]):
            return False
        
        temp = board[r][c]
        board[r][c] = '#'
        found = (dfs(r+1, c, idx+1) or dfs(r-1, c, idx+1) or
                 dfs(r, c+1, idx+1) or dfs(r, c-1, idx+1))
        board[r][c] = temp
        return found
    
    for r in range(rows):
        for c in range(cols):
            if dfs(r, c, 0):
                return True
    return False

Complexity Analysis

• Time: O(M * N * 4^L) where M*N is the grid size and L is the word length. From each cell, we branch into at most 4 directions for L levels (actually 3 after the first step since we don’t go back).
• Space: O(L) for the recursion stack. We modify the board in-place for visited tracking.

The 4^L factor is the worst case but rarely reached. In practice, character mismatches prune most branches early.

Word Search II / Boggle Solver (LeetCode 212)

Given a grid and a list of words, find all words that exist in the grid. Using the single-word search for each word separately is too slow. Instead, build a Trie from all words and search the grid once, following Trie branches.

Building the Trie

class TrieNode:
    def __init__(self):
        self.children = {}
        self.word = None  # stores the complete word at leaf
    
def build_trie(words: list[str]) -> TrieNode:
    root = TrieNode()
    for word in words:
        node = root
        for char in word:
            if char not in node.children:
                node.children[char] = TrieNode()
            node = node.children[char]
        node.word = word
    return root

Searching with Trie

def findWords(board: list[list[str]], words: list[str]) -> list[str]:
    """
    LeetCode 212: Find all words from list in grid using Trie.
    """
    root = build_trie(words)
    rows, cols = len(board), len(board[0])
    result = []
    
    def dfs(r: int, c: int, node: TrieNode):
        if r < 0 or r >= rows or c < 0 or c >= cols:
            return
        
        char = board[r][c]
        if char not in node.children:
            return
        
        next_node = node.children[char]
        
        # Found a complete word
        if next_node.word is not None:
            result.append(next_node.word)
            next_node.word = None  # avoid duplicates
        
        # Mark visited
        board[r][c] = '#'
        
        # Explore neighbors
        dfs(r+1, c, next_node)
        dfs(r-1, c, next_node)
        dfs(r, c+1, next_node)
        dfs(r, c-1, next_node)
        
        # Backtrack
        board[r][c] = char
        
        # Optimization: prune empty Trie branches
        if not next_node.children:
            del node.children[char]
    
    for r in range(rows):
        for c in range(cols):
            dfs(r, c, root)
    
    return result

Why the Trie Matters

Without a Trie, searching for K words each of length L on an M*N grid takes O(K * M * N * 4^L). With a Trie, all words share common prefixes. If “apple” and “apply” are both in the list, the path “appl” is explored only once. Dead branches are pruned early: if the Trie has no child for the current character, we stop immediately.

Trie Pruning Optimization

The line if not next_node.children: del node.children[char] is crucial. After finding a word, if a Trie node has no remaining children, we remove it. This prevents re-exploring dead branches on subsequent grid cells. For large word lists, this optimization makes a significant difference.

Complexity

• Time: O(M * N * 4^L) in the worst case, but the Trie prunes extensively in practice.
• Space: O(sum of word lengths) for the Trie, plus O(L) for recursion.

Word Ladder (LeetCode 127)

Given a start word, an end word, and a dictionary, find the shortest transformation sequence where each step changes exactly one letter and the resulting word must be in the dictionary.

BFS Approach

Each word is a node. Two words are connected if they differ by exactly one character. BFS finds the shortest path.

from collections import deque, defaultdict

def ladderLength(beginWord: str, endWord: str, 
                  wordList: list[str]) -> int:
    """
    LeetCode 127: BFS word ladder.
    Returns length of shortest transformation sequence.
    """
    word_set = set(wordList)
    if endWord not in word_set:
        return 0
    
    queue = deque([(beginWord, 1)])
    visited = {beginWord}
    
    while queue:
        word, length = queue.popleft()
        
        if word == endWord:
            return length
        
        # Try changing each position to each letter
        for i in range(len(word)):
            for c in 'abcdefghijklmnopqrstuvwxyz':
                next_word = word[:i] + c + word[i+1:]
                if next_word in word_set and next_word not in visited:
                    visited.add(next_word)
                    queue.append((next_word, length + 1))
    
    return 0

Optimized: Pattern-Based Adjacency

Instead of trying all 26 letters at each position, precompute adjacency using wildcard patterns. For “hot”, the patterns are “ot”, “ht”, “ho*”. Words sharing a pattern are neighbors.

def ladderLength_optimized(beginWord: str, endWord: str,
                            wordList: list[str]) -> int:
    """Word ladder with pattern-based neighbor lookup."""
    word_set = set(wordList)
    if endWord not in word_set:
        return 0
    
    # Build pattern -> words mapping
    L = len(beginWord)
    patterns = defaultdict(list)
    for word in word_set:
        for i in range(L):
            pattern = word[:i] + '*' + word[i+1:]
            patterns[pattern].append(word)
    
    queue = deque([(beginWord, 1)])
    visited = {beginWord}
    
    while queue:
        word, length = queue.popleft()
        
        for i in range(L):
            pattern = word[:i] + '*' + word[i+1:]
            for neighbor in patterns[pattern]:
                if neighbor == endWord:
                    return length + 1
                if neighbor not in visited:
                    visited.add(neighbor)
                    queue.append((neighbor, length + 1))
            # Clear to avoid revisiting
            patterns[pattern] = []
    
    return 0

Bidirectional BFS

For even faster results, search from both ends simultaneously. When the two frontiers meet, you have found the shortest path.

def ladderLength_bidirectional(beginWord: str, endWord: str,
                                wordList: list[str]) -> int:
    """Bidirectional BFS for word ladder."""
    word_set = set(wordList)
    if endWord not in word_set:
        return 0
    
    front = {beginWord}
    back = {endWord}
    visited = set()
    length = 1
    
    while front and back:
        # Always expand the smaller frontier
        if len(front) > len(back):
            front, back = back, front
        
        next_front = set()
        for word in front:
            for i in range(len(word)):
                for c in 'abcdefghijklmnopqrstuvwxyz':
                    next_word = word[:i] + c + word[i+1:]
                    
                    if next_word in back:
                        return length + 1
                    
                    if next_word in word_set and next_word not in visited:
                        visited.add(next_word)
                        next_front.add(next_word)
        
        front = next_front
        length += 1
    
    return 0

Bidirectional BFS reduces the search space from O(b^d) to O(b^(d/2)) where b is the branching factor and d is the depth.

Word Ladder II (LeetCode 126)

Find ALL shortest transformation sequences.

def findLadders(beginWord: str, endWord: str,
                 wordList: list[str]) -> list[list[str]]:
    """
    LeetCode 126: Find all shortest word ladders.
    BFS to find distances, then DFS to reconstruct paths.
    """
    word_set = set(wordList)
    if endWord not in word_set:
        return []
    
    # BFS to build distance map
    dist = {beginWord: 0}
    queue = deque([beginWord])
    found = False
    
    while queue and not found:
        level_size = len(queue)
        level_words = set()
        
        for _ in range(level_size):
            word = queue.popleft()
            for i in range(len(word)):
                for c in 'abcdefghijklmnopqrstuvwxyz':
                    next_word = word[:i] + c + word[i+1:]
                    if next_word == endWord:
                        found = True
                    if next_word in word_set and next_word not in dist:
                        level_words.add(next_word)
        
        for w in level_words:
            dist[w] = dist[word] + 1
            queue.append(w)
    
    if not found:
        return []
    
    # DFS to find all shortest paths
    result = []
    
    def dfs(word, path):
        if word == endWord:
            result.append(path[:])
            return
        
        for i in range(len(word)):
            for c in 'abcdefghijklmnopqrstuvwxyz':
                next_word = word[:i] + c + word[i+1:]
                if next_word in dist and dist[next_word] == dist[word] + 1:
                    path.append(next_word)
                    dfs(next_word, path)
                    path.pop()
    
    dfs(beginWord, [beginWord])
    return result

Pattern Recognition

These three problems share a common structure but differ in traversal strategy:

Problem	Graph Model	Traversal	Key Data Structure
Word Search	Grid cells are nodes	DFS + backtrack	In-place marking
Boggle/Word Search II	Grid cells are nodes	DFS + backtrack	Trie for multi-word
Word Ladder	Words are nodes	BFS	Set for word lookup

When to Use Each Pattern

• Single word in grid: DFS + backtracking from each matching start cell.
• Multiple words in grid: Build a Trie, DFS once with Trie guidance.
• Transform word A to word B: BFS on the word graph, each word is a node.
• All shortest transformations: BFS for distances, then DFS for path reconstruction.

Complexity Summary

Problem	Time	Space
Word Search	O(MN4^L)	O(L)
Word Search II (Trie)	O(MN4^L) worst, much better in practice	O(sum of word lengths)
Word Ladder (BFS)	O(M^2 * N) where M=word length, N=word count	O(M * N)
Word Ladder (Bidirectional)	O(M^2 * N) but faster constant	O(M * N)

Practice Problems

Problem	Difficulty	Pattern
LeetCode 79: Word Search	Medium	DFS backtracking
LeetCode 212: Word Search II	Hard	Trie + DFS
LeetCode 127: Word Ladder	Hard	BFS word graph
LeetCode 126: Word Ladder II	Hard	BFS + DFS paths
LeetCode 980: Unique Paths III	Hard	DFS backtracking grid
LeetCode 472: Concatenated Words	Hard	Trie + DFS

Key Takeaways

1. Backtracking is essential for word search. Mark cells visited before recursing, restore them after returning.
2. Trie turns K single-word searches into one multi-word search. Common prefixes are explored only once.
3. Prune aggressively. Remove found words from Trie, check character frequencies before starting, and search from the rarer end.
4. Word ladder is a graph problem where words are nodes. BFS gives the shortest transformation length.
5. Bidirectional BFS dramatically reduces search space for word ladder by searching from both ends.