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. Consider the following Python code snippet implementing the optimal backtracking approach for Expression Add Operators. Given input num = "123" and target = 6, what is the content of the result list after the function completes?

from typing import List

def addOperators(num: str, target: int) -> List[str]:
    res = []
    path = []
    def backtrack(index: int, evaluated: int, last_operand: int):
        if index == len(num):
            if evaluated == target:
                res.append(''.join(path))
            return
        for i in range(index, len(num)):
            if i != index and num[index] == '0':
                break
            curr_str = num[index:i+1]
            curr = int(curr_str)
            length_before = len(path)
            if index == 0:
                path.append(curr_str)
                backtrack(i+1, curr, curr)
                path[length_before:] = []
            else:
                path.append('+'); path.append(curr_str)
                backtrack(i+1, evaluated + curr, curr)
                path[length_before:] = []
    backtrack(0, 0, 0)
    return res

easy

A. ["1+23", "12+3"]

B. ["123"]

C. ["1+2+3", "123"]

D. ["1+2+3"]

Solution

1. Step 1: Trace backtracking calls for num="123", target=6

   At index=0, path starts with "1". Then at index=1, add '+' and "2", evaluated=3. Then at index=2, add '+' and "3", evaluated=6, matches target, so "1+2+3" is added.

2. Step 2: Check other possible expressions

   "123" alone evaluates to 123, not 6. "1+23"=24, "12+3"=15, none equal 6. So only "1+2+3" is in result.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Only "1+2+3" sums to 6 [OK]

Hint: Only "1+2+3" equals 6 with given operators [OK]

Common Mistakes:

• Assuming "123" or "1+23" equals target

2. Consider the following buggy code for generating letter combinations. Which line contains the subtle bug that causes incorrect or incomplete results?

from collections import deque

def letterCombinations(digits):
    if digits == '':
        return ['']
    digit_map = {'2': 'abc', '3': 'def', '4': 'ghi', '5': 'jkl',
                 '6': 'mno', '7': 'pqrs', '8': 'tuv', '9': 'wxyz'}
    queue = deque([''])
    for digit in digits:
        letters = digit_map[digit]
        for _ in range(len(queue)):
            prev = queue.popleft()
            for char in letters:
                queue.append(prev + char)
    return list(queue)

medium

A. Line 7: letters = digit_map[digit]

B. Line 2: if digits == '': return ['']

C. Line 10: prev = queue.popleft()

D. Line 1: from collections import deque

Solution

1. Step 1: Analyze empty input handling

   Returning [''] for empty input is incorrect; the problem expects an empty list [] when input is empty.

2. Step 2: Check other lines

   Digit mapping, queue operations, and imports are correct and do not cause bugs.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Empty input should return [] not [''] to match problem spec [OK]

Hint: Empty input must return empty list, not list with empty string [OK]

Common Mistakes:

• Returning [''] instead of [] for empty input
• Assuming digits '1' or '0' map to letters

3. Suppose the N-Queens problem is modified so that queens can be placed multiple times in the same column (i.e., column constraint is relaxed), but diagonal attacks still apply. Which modification to the bitmask backtracking algorithm correctly adapts to this variant?

hard

A. Remove the column bitmask tracking and only track diagonal attacks in recursion

B. Keep column bitmask but allow multiple queens by resetting it each row

C. Use a greedy approach placing queens in any column without pruning

D. Track columns as before but ignore diagonal bitmasks

Solution

1. Step 1: Understand relaxed constraints

   Since columns can have multiple queens, column bitmask is no longer needed to prune placements.

2. Step 2: Adapt pruning to only diagonal attacks

   Keep diag1 and diag2 bitmasks to prune diagonal conflicts, but remove column mask from available_positions calculation.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Removing column mask allows multiple queens per column while still pruning diagonals [OK]

Hint: Relaxed constraints remove column pruning, keep diagonal pruning [OK]

Common Mistakes:

• Resetting column mask each row incorrectly
• Ignoring diagonal pruning
• Using greedy without pruning

4. Suppose you want to modify the palindrome partitioning algorithm to allow reuse of substrings in partitions (i.e., substrings can appear multiple times in different partitions). Which change to the algorithm is necessary to correctly handle this variant without losing valid partitions or causing duplicates?

hard

A. Memoize palindrome checks and reuse results but keep backtracking unchanged

B. Modify backtracking to avoid popping from path to reuse substrings across calls

C. Use a global visited set to skip substrings already used in previous partitions

D. Allow substrings to be reused by resetting path after each complete partition

Solution

1. Step 1: Understand reuse requirement

   Reusing substrings means substrings can appear multiple times in different partitions, so path management must allow multiple uses.

2. Step 2: Identify necessary algorithm change

   Memoizing palindrome checks improves efficiency by avoiding repeated palindrome computations, while backtracking logic remains unchanged to generate all valid partitions.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Memoization optimizes palindrome checks without affecting partition generation correctness [OK]

Hint: Memoize palindrome checks to optimize without changing backtracking [OK]

Common Mistakes:

• Assuming popping affects substring reuse
• Using visited sets that block valid reuse
• Resetting path incorrectly losing partitions

5. Suppose you want to generate all permutations of an array where elements can be repeated any number of times (i.e., unlimited reuse of elements). Which modification to the standard backtracking approach is correct?

hard

A. Remove the used array entirely and allow elements to be chosen multiple times at each recursion level

B. Use the same backtracking with a used array but reset used[i] to false only after the entire recursion finishes

C. Use in-place swapping but skip swapping elements that have been used before in the current recursion path

D. Generate permutations normally and then filter out duplicates after generation

Solution

1. Step 1: Understand the problem variant

   Elements can be reused unlimited times, so no need to track usage.

2. Step 2: Modify backtracking accordingly

   Removing the used array allows choosing any element at each recursion level multiple times, generating permutations with repetition.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Allowing repeated choices without usage tracking fits unlimited reuse [OK]

Hint: Unlimited reuse means no used array needed [OK]

Common Mistakes:

• Keeping used array causes missing permutations or incorrect pruning