Word Search II (Trie + Backtrack)

▶

Steps

setup

Build Trie - insert 'eat'

Insert word 'eat' into the trie. Root → e(id=1) → a(id=2) → t(id=3, word='eat'). Three nodes created along the path.

💡 The trie stores all search words as paths from root. Each character gets its own node.

Line:

for w in words:
    node = root
    for c in w:
        if c not in node.children:
            node.children[c] = TrieNode()
        node = node.children[c]
    node.word = w

💡 Inserting 'eat' creates nodes for e→a→t with word='eat' at the leaf.

setup

Build Trie - insert 'oath'

Insert word 'oath'. Root → o(id=4) → a(id=5) → t(id=6) → h(id=7, word='oath'). Four nodes created.

💡 Notice 'oath' shares no prefix with 'eat' so a completely separate branch is created from root.

Line:

for c in w:
    if c not in node.children:
        node.children[c] = TrieNode()
    node = node.children[c]
node.word = w

💡 Root now has two children: e (for eat) and o (for oath). Each word occupies its own branch.

search

DFS from cell (1,1)='t' - no trie match, prune

Start DFS at board[1][1]='t'. Check if root has child 't' - it does not. Prune immediately without exploring neighbors.

💡 This is the power of the trie: if the first character doesn't match any word prefix we skip the entire DFS subtree from this cell.

Line:

def backtrack(r, c, node):
    letter = board[r][c]
    currNode = node.children.get(letter)
    if not currNode:
        return  # prune

💡 No word starts with 't' so this cell is useless as a starting point.

search

DFS from cell (1,3)='e' - match 'e', continue

Start DFS at board[1][3]='e'. Root has child 'e' (id=1). Mark board[1][3]='#', move to trie node e.

💡 'e' is the start of 'eat'. We mark the cell '#' to prevent revisiting it in the same DFS path.

Line:

board[r][c] = '#'
for dr, dc in [(1,0),(-1,0),(0,1),(0,-1)]:
    nr, nc = r + dr, c + dc

💡 The cell is marked '#' as a visited guard. After backtracking it will be restored to 'e'.

search

DFS from (1,3)→(0,3)='a' - match 'a', continue

From board[1][3]='#' (was 'e'), check neighbor board[0][3]='a'. Trie node e has child 'a' (id=2). Mark board[0][3]='#', move to trie node a.

💡 We're building the word 'e→a'. The path so far on the board is (1,3)→(0,3).

Line:

currNode = node.children.get(letter)
if not currNode: return
board[r][c] = '#'

💡 The active_path now shows root→e→a. One more character needed to complete 'eat'.

search

DFS from (0,3)→(1,3) blocked - try (0,2)='a' - no 't'

(1,3) is '#' (already visited). Try neighbor (0,2)='a' - trie node 'a' has no child 'a'. Try (0,2)='a' is also not 't'. Need 't' but only neighbors are '#' or 'a'. No match on any side - backtrack.

💡 The board path e→a at (1,3)→(0,3) has no neighboring 't'. We must backtrack and restore both cells.

Line:

board[r][c] = letter  # restore after backtrack
if not currNode.children:
    node.children.pop(letter)  # prune trie

💡 Backtracking restores cells so other DFS paths can use them. This is the key backtracking step.

search

DFS from cell (1,3)='e' → neighbor (1,2)='a' → (1,1) was 't' - find 'eat'!

Restart from board[1][3]='e'. Move to neighbor (1,2)='a' (trie: e→a). From (1,2) move to neighbor (1,1)='t' (trie: a→t, word='eat'). Word found! Append 'eat' to result. Set currNode.word=None to prevent re-finding.

💡 This is the successful path: e(1,3) → a(1,2) → t(1,1). The trie guides us to recognize the complete word at t.

Line:

if currNode.word:
    result.append(currNode.word)
    currNode.word = None  # prevent duplicate

💡 Setting word=None on the found trie node ensures 'eat' is never added twice even if there's another path spelling it.

search

DFS from cell (0,0)='o' - match 'o', start 'oath' search

Scan all board cells for new starting characters. Cell (0,0)='o' matches root child 'o' (id=4). Mark board[0][0]='#', move to trie node o.

💡 We found the start of 'oath'. Now we need 'a' from a neighbor of (0,0).

Line:

for r in range(rows):
    for c in range(cols):
        backtrack(r, c, root)

💡 The full board scan ensures we try every possible starting position for words.

search

(0,0)→(1,0)='e' - no 'a' child for 'o' branch

From (0,0)='#', try neighbor (1,0)='e'. Trie node 'o' has no 'e' child. Try (0,1)='a' - trie node 'o' has 'a' child (id=5). Match! Move to (0,1).

💡 We skip (1,0) immediately because trie node 'o' has no 'e' child. The trie prunes bad directions instantly.

Line:

currNode = node.children.get(letter)
if not currNode:
    return

💡 Going right to (0,1)='a' matches the trie. Path: o(0,0)→a(0,1).

search

(0,1)→(1,1)='t' - match 't', one step closer

From (0,1)='a', check neighbors. (1,1)='t' - trie node 'a' (child of 'o') has 't' child (id=6). Match! Mark (1,1)='#', move to trie node t.

💡 Third character 't' found. Path so far: o(0,0)→a(0,1)→t(1,1). Need 'h' to complete 'oath'.

Line:

board[r][c] = '#'
backtrack(nr, nc, currNode)

💡 Three of four characters matched. One more hop to find 'h'.

search

(1,1)→(2,1)='h' - find 'oath'! Prune trie node

From (1,1)='t', check neighbor (2,1)='h'. Trie node 't' has 'h' child (id=7, word='oath'). Word found! Append 'oath' to result. Set word=None. Node 7 has no children → prune it from trie (pop 'h' from t's children).

💡 Found 'oath' via path (0,0)→(0,1)→(1,1)→(2,1). The trie prunes the leaf node immediately since it has no children and the word is consumed.

Line:

if currNode.word:
    result.append(currNode.word)
    currNode.word = None
...
if not currNode.children:
    node.children.pop(letter)

💡 Pruning the empty leaf makes the trie smaller and future searches faster. If no words share the 'o→a→t→h' prefix, the entire branch can disappear.

from typing import List

class TrieNode:
    def __init__(self):
        self.children = {}
        self.word = None

class Solution:
    def buildTrie(self, words):
        root = TrieNode()
        for w in words:
            node = root
            for c in w:
                if c not in node.children:
                    node.children[c] = TrieNode()
                node = node.children[c]
            node.word = w
        return root

    def findWords(self, board: List[List[str]], words: List[str]) -> List[str]:
        root = self.buildTrie(words)
        rows, cols = len(board), len(board[0])
        result = []

        def backtrack(r, c, node):
            letter = board[r][c]
            currNode = node.children.get(letter)
            if not currNode:
                return
            if currNode.word:
                result.append(currNode.word)
                currNode.word = None

            board[r][c] = '#'
            for dr, dc in [(1,0),(-1,0),(0,1),(0,-1)]:
                nr, nc = r + dr, c + dc
                if 0 <= nr < rows and 0 <= nc < cols and board[nr][nc] != '#':
                    backtrack(nr, nc, currNode)
            board[r][c] = letter

            if not currNode.children:
                node.children.pop(letter)

        for r in range(rows):
            for c in range(cols):
                backtrack(r, c, root)

        return result

# Driver code
if __name__ == '__main__':
    board = [
        ['o','a','a','n'],
        ['e','t','a','e'],
        ['i','h','k','r'],
        ['i','f','l','v']
    ]
    words = ['oath','pea','eat','rain']
    sol = Solution()
    print(sol.findWords(board, words))

📊

Word Search II - Watch the Trie + Backtracking Execute, Step by Step

The trie acts as a combined dictionary and prefix checker - instead of checking all words per cell, we follow one trie path that matches the board. When the trie has no child for a board character we prune immediately.

insert

eat

◉eat*

insert

oath

◉eoath*

search

t

◉

Search: false

search

e

◉e

search

ea

◉ea

search

e

◉e

search

eat

◉eat*

Pairs found: 1

Search: true

search

o

◉o

Pairs found: 1

search

oa

◉oa

Pairs found: 1

search

oat

◉oat

Pairs found: 1

find_pairs

oath

◉oh*

Pairs found: 2

Search: true

Key Takeaways

✓ Building a trie from all words allows prefix-based pruning - if no word starts with a board character the DFS is skipped entirely.

Without a trie you'd check each word against each board path separately, which is much slower.

✓ Marking cells '#' during DFS prevents revisiting the same cell in one path, ensuring valid board paths only.

The restore step (board[r][c] = letter) after backtracking lets other DFS paths reuse the cell.

✓ Pruning trie nodes with no children after finding a word avoids re-finding the same word and shrinks future search space.

This optimization is subtle but powerful - the trie gets smaller as words are found.

Practice

1. You are given a numeric string and a target integer. You need to insert binary operators (+, -, *) between digits to form expressions that evaluate to the target. Which algorithmic approach guarantees finding all valid expressions efficiently while handling operator precedence and avoiding invalid operands like those with leading zeros?

easy

A. Backtracking with pruning and careful operand parsing to explore all operator insertions

B. Breadth-first search enumerating all possible expressions without pruning

C. Dynamic programming that stores sub-expression results without operator precedence handling

D. Greedy approach that inserts operators at fixed intervals without backtracking

Solution

1. Step 1: Understand problem requirements

   The problem requires exploring all ways to insert operators to reach a target, respecting operator precedence and avoiding invalid operands like those with leading zeros.

2. Step 2: Identify suitable algorithm

   Backtracking with pruning and operand parsing systematically explores all valid expressions, correctly handles precedence (especially multiplication), and prunes invalid paths early.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Backtracking explores all valid expressions with pruning [OK]

Hint: Backtracking explores all operator insertions with pruning [OK]

Common Mistakes:

• Assuming greedy or DP can handle operator precedence and invalid operands

2. You need to generate all combinations of balanced parentheses pairs for a given number n. Which algorithmic approach guarantees generating only valid sequences without generating invalid ones first?

easy

A. Brute force: generate all possible sequences of '(' and ')' of length 2n, then filter valid ones

B. Backtracking with pruning: build sequences by adding '(' or ')' only when it keeps the sequence valid

C. Greedy approach: always add '(' until n is reached, then add ')' to close all opened parentheses

D. Dynamic programming: count the number of valid sequences using Catalan number formula

Solution

1. Step 1: Understand problem constraints

   We want to generate all valid parentheses sequences without generating invalid ones first.

2. Step 2: Analyze approaches

   Brute force generates all sequences including invalid ones, greedy fails to generate all valid sequences, DP counts sequences but does not generate them. Backtracking with pruning adds '(' or ')' only when valid, thus generating only valid sequences.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Backtracking with pruning avoids invalid sequences [OK]

Hint: Backtracking prunes invalid sequences early [OK]

Common Mistakes:

• Thinking greedy can generate all valid sequences
• Confusing counting with generating sequences

3. You need to count all distinct ways to place n queens on an nxn chessboard so that no two queens threaten each other. Which algorithmic approach guarantees finding all valid solutions efficiently by exploring partial placements and pruning invalid ones early?

easy

A. Backtracking that tries all column placements per row and abandons invalid partial boards

B. Greedy algorithm that places queens row by row choosing the first safe column

C. Dynamic programming that stores counts of valid queen placements per row without conflict checks

D. Breadth-first search enumerating all board states level by level

Solution

1. Step 1: Understand problem constraints

   The problem requires counting all valid queen placements with no conflicts, which demands exploring all possibilities.

2. Step 2: Identify suitable algorithm

   Backtracking systematically tries each column per row and abandons partial solutions that violate constraints, ensuring correctness and pruning search space.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Backtracking explores all valid configurations efficiently [OK]

Hint: Counting all valid placements requires backtracking [OK]

Common Mistakes:

• Assuming greedy placement always works
• Believing DP without conflict checks suffices

4. Given the following code for palindrome partitioning, what is the final output when input string s = "aab" is passed to partition(s)?

def partition(s):
    def is_palindrome(left, right):
        while left < right:
            if s[left] != s[right]:
                return False
            left += 1
            right -= 1
        return True

    def backtrack(start, path):
        if start == len(s):
            result.append(path[:])
            return
        for end in range(start, len(s)):
            if is_palindrome(start, end):
                path.append(s[start:end+1])
                backtrack(end+1, path)
                path.pop()

    result = []
    backtrack(0, [])
    return result

easy

A. [["a", "a", "b"]]

B. [["a", "ab"], ["aa", "b"]]

C. [["a", "a", "b"], ["aa", "b"]]

D. [["aab"]]

Solution

1. Step 1: Trace backtrack calls for s="aab"

   Start=0, path=[]; check substrings: "a" (palindrome), "aa" (palindrome), "aab" (not palindrome). Explore "a" -> backtrack(1, ["a"]), then "a" -> backtrack(2, ["a", "a"]), then "b" -> backtrack(3, ["a", "a", "b"]) adds ["a", "a", "b"] to result.

2. Step 2: Explore "aa" substring

   From start=0, choose "aa" -> backtrack(2, ["aa"]), then "b" -> backtrack(3, ["aa", "b"]) adds ["aa", "b"] to result.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Both partitions contain only palindromes and cover entire string [OK]

Hint: Trace recursion and palindrome checks carefully [OK]

Common Mistakes:

• Including non-palindromic substrings like "ab"
• Missing one valid partition
• Returning partial partitions

5. You are given a 2D grid of characters and a target string. You need to determine if the string can be formed by sequentially adjacent cells (horizontally or vertically) without revisiting any cell. Which algorithmic approach best guarantees an optimal solution for this problem?

easy

A. Backtracking with in-place marking and exploring all four directions

B. Dynamic Programming with memoization to store partial matches

C. Greedy search by always choosing the next matching character closest to the start

D. Breadth-first search (BFS) to explore all possible paths simultaneously

Solution

1. Step 1: Understand problem constraints

   The problem requires checking if a word can be formed by adjacent cells without reuse, which is a classic backtracking scenario.

2. Step 2: Identify suitable algorithm

   Backtracking with in-place marking efficiently explores all paths while preventing revisiting cells, guaranteeing correctness and optimal pruning.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Backtracking explores all valid paths with pruning [OK]

Hint: Backtracking fits adjacency and no-reuse constraints [OK]

Common Mistakes:

• Assuming greedy or DP can solve adjacency constraints optimally