Word Search II

▶

Steps

setup

Build Trie Root Node

Initialize the root of the trie as an empty node with no children and no word assigned.

💡 The trie root is the starting point for inserting all words, enabling efficient prefix searches.

Line:

root = TrieNode()

💡 A single root node will hold all word prefixes, allowing shared traversal paths.

setup

Insert Word 'oath' into Trie

Insert the word 'oath' character by character into the trie, creating child nodes as needed.

💡 Inserting words builds the trie structure that enables prefix-based pruning during search.

Line:

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

💡 Each character extends the trie path; shared prefixes will reuse nodes.

setup

Insert Word 'pea' into Trie

Insert the word 'pea' into the trie similarly, creating new child nodes for characters 'p', 'e', and 'a'.

💡 Adding all words to the trie allows the search to quickly reject paths not matching any prefix.

Line:

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

💡 Words with different prefixes create separate branches in the trie.

setup

Insert Word 'eat' into Trie

Insert the word 'eat' into the trie, sharing the 'e' node if it exists, then adding 'a' and 't'.

💡 Shared prefixes reduce trie size and speed up search by grouping common paths.

Line:

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

💡 The 'e' node is shared between 'pea' and 'eat', demonstrating prefix sharing.

setup

Insert Word 'rain' into Trie

Insert the word 'rain' into the trie, creating new nodes for 'r', 'a', 'i', and 'n'.

💡 Words with unique prefixes add new branches to the trie.

Line:

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

💡 The trie now fully represents all words to be searched.

traverse

Start Backtracking from Cell (0,0) 'o'

Begin backtracking from board cell (0,0) with letter 'o', which matches a child of the trie root.

💡 Starting backtracking only from cells matching trie root children avoids unnecessary searches.

Line:

for r in range(ROWS):
    for c in range(COLS):
        backtrack(r, c, root)

💡 Backtracking initiates only on promising starting letters.

shrink

Mark Cell (0,0) as Visited

Mark the current cell (0,0) as visited by replacing 'o' with '#' to avoid revisiting during this path.

💡 Marking visited cells prevents cycles and repeated use of the same letter in one word path.

Line:

board[r][c] = '#'

💡 In-place marking is space efficient and reversible after backtracking.

traverse

Explore Neighbor Cell (0,1) 'a'

Move to the right neighbor cell (0,1) with letter 'a', which is a child of the current trie node for 'o'.

💡 Exploring neighbors extends the current prefix path in the trie.

Line:

for (nr, nc) in [(r+1,c),(r-1,c),(r,c+1),(r,c-1)]:
    if 0 <= nr < ROWS and 0 <= nc < COLS and board[nr][nc] != '#':
        backtrack(nr, nc, curr_node)

💡 Backtracking follows trie children to build words letter by letter.

traverse

Explore Neighbor Cell (1,1) 't'

From (0,1), move down to (1,1) with letter 't', continuing the trie path for 'oath'.

💡 Moving to adjacent cells extends the current word candidate.

Line:

for (nr, nc) in [(r+1,c),(r-1,c),(r,c+1),(r,c-1)]:
    if 0 <= nr < ROWS and 0 <= nc < COLS and board[nr][nc] != '#':
        backtrack(nr, nc, curr_node)

💡 Backtracking explores all valid adjacent paths to find words.

traverse

Explore Neighbor Cell (1,2) 'a'

From (1,1), move right to (1,2) with letter 'a', continuing the trie path for 'oath'.

💡 Continuing to adjacent cells builds the candidate word.

Line:

for (nr, nc) in [(r+1,c),(r-1,c),(r,c+1),(r,c-1)]:
    if 0 <= nr < ROWS and 0 <= nc < COLS and board[nr][nc] != '#':
        backtrack(nr, nc, curr_node)

💡 The search path is following the trie nodes to form words.

compare

Explore Neighbor Cell (2,2) 'k' - Dead End

From (1,2), attempt to move down to (2,2) with letter 'k', which is not a child of current trie node, so backtrack.

💡 Dead ends prune the search path early, avoiding unnecessary exploration.

Line:

curr_node = parent.children.get(letter)
if not curr_node:
    return

💡 Trie structure quickly rejects invalid paths.

insert

Find Word 'oath' at Cell (2,1) 'h'

From (1,2), move down to (2,1) with letter 'h', which completes the word 'oath' in the trie; add 'oath' to results.

💡 When a trie node contains a word, it means a valid word is found on the board.

Line:

if curr_node.word:
    res.append(curr_node.word)
    curr_node.word = None

💡 Words are recorded exactly once during backtracking.

expand

Restore Cell (2,1) Letter 'h' After Backtracking

After exploring neighbors from (2,1), restore the original letter 'h' to allow other paths to use this cell.

💡 Restoring letters ensures the board state is correct for other backtracking paths.

Line:

board[r][c] = letter

💡 Backtracking cleans up after itself to maintain correctness.

prune

Prune Trie Node for 'h' After Word Found

Since the 'h' node has no children after word removal, prune it from its parent to optimize future searches.

💡 Pruning reduces trie size, speeding up subsequent backtracking calls.

Line:

if not curr_node.children:
    parent.children.pop(letter)

💡 Trie pruning dynamically optimizes the search space.

traverse

Start Backtracking from Cell (1,1) 't' for Word 'eat'

Begin backtracking from cell (1,1) with letter 't', which is a child of the trie root for the word 'eat'.

💡 Backtracking starts from all cells matching trie root children to find all words.

Line:

for r in range(ROWS):
    for c in range(COLS):
        backtrack(r, c, root)

💡 Multiple starting points are explored to find all valid words.

shrink

Mark Cell (1,1) as Visited

Mark cell (1,1) as visited by replacing 't' with '#' to avoid revisiting during this path.

💡 Marking visited cells prevents cycles in the current search path.

Line:

board[r][c] = '#'

💡 In-place marking is efficient and reversible.

traverse

Explore Neighbor Cell (1,2) 'a'

From (1,1), move right to (1,2) with letter 'a', continuing the trie path for 'eat'.

💡 Exploring neighbors extends the current word candidate.

Line:

for (nr, nc) in [(r+1,c),(r-1,c),(r,c+1),(r,c-1)]:
    if 0 <= nr < ROWS and 0 <= nc < COLS and board[nr][nc] != '#':
        backtrack(nr, nc, curr_node)

💡 Backtracking follows trie children to build words letter by letter.

traverse

Explore Neighbor Cell (0,2) 'a'

From (1,2), move up to (0,2) with letter 'a', continuing the trie path for 'eat'.

💡 Backtracking explores all valid adjacent cells.

Line:

for (nr, nc) in [(r+1,c),(r-1,c),(r,c+1),(r,c-1)]:
    if 0 <= nr < ROWS and 0 <= nc < COLS and board[nr][nc] != '#':
        backtrack(nr, nc, curr_node)

💡 The search path is exploring multiple directions for word completion.

insert

Find Word 'eat' at Cell (1,0) 'e'

From (0,2), move down-left to (1,0) with letter 'e', completing the word 'eat'; add 'eat' to results.

💡 Finding a word adds it to the result and removes it from the trie to avoid duplicates.

Line:

if curr_node.word:
    res.append(curr_node.word)
    curr_node.word = None

💡 Words are recorded exactly once during backtracking.

reconstruct

Final Result After Full Board Search

After backtracking from all cells, the final list of found words is ['oath', 'eat'].

💡 The algorithm completes after exploring all starting points and pruning the trie.

Line:

return res

💡 The algorithm efficiently finds all valid words on the board.

from typing import List

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

class Solution:
    def findWords(self, board: List[List[str]], words: List[str]) -> List[str]:
        root = TrieNode()  # STEP 1
        for word in words:  # STEP 2-5
            node = root
            for char in word:
                if char not in node.children:
                    node.children[char] = TrieNode()
                node = node.children[char]
            node.word = word

        ROWS, COLS = len(board), len(board[0])
        res = []

        def backtrack(r, c, parent):
            letter = board[r][c]
            curr_node = parent.children.get(letter)
            if not curr_node:
                return  # STEP 11

            if curr_node.word:
                res.append(curr_node.word)  # STEP 12
                curr_node.word = None

            board[r][c] = '#'  # STEP 7, 16
            for (nr, nc) in [(r+1,c),(r-1,c),(r,c+1),(r,c-1)]:
                if 0 <= nr < ROWS and 0 <= nc < COLS and board[nr][nc] != '#':
                    backtrack(nr, nc, curr_node)  # STEP 8,9,10,17,18,19
            board[r][c] = letter  # STEP 13

            if not curr_node.children:
                parent.children.pop(letter)  # STEP 14

        for r in range(ROWS):  # STEP 6,15
            for c in range(COLS):
                backtrack(r, c, root)

        return res  # STEP 20

📊

Word Search II - Watch the Algorithm Execute, Step by Step

Watching each step of the backtracking combined with trie traversal reveals how the algorithm efficiently finds words without redundant searches.

setup

Result: []

insert

i

o

0

a

1

t

2

h

3

Result: []

insert

i

p

0

e

1

a

2

Result: []

insert

i

e

0

a

1

t

2

Result: []

insert

i

r

0

a

1

i

2

n

3

Result: []

compare

c

o

0

a

1

a

2

n

3

Result: []

move_right

c

#

0

a

1

a

2

n

3

Result: []

compare

r

#

0

c

a

1

a

2

n

3

Result: []

compare

e

0

c

t

1

a

2

e

3

Result: []

compare

e

0

r

t

1

c

a

2

e

3

Result: []

compare

i

0

h

1

c

k

2

r

3

Result: []

record

i

0

c

h

1

r

k

2

r

3

Result: ["oath"]

move_left

i

0

c

h

1

r

k

2

r

3

Result: ["oath"]

prune

Result: ["oath"]

compare

e

0

c

t

1

a

2

e

3

Result: ["oath"]

move_right

e

0

c

#

1

a

2

e

3

Result: ["oath"]

compare

e

0

r

#

1

c

a

2

e

3

Result: ["oath"]

compare

r

o

0

a

1

c

a

2

n

3

Result: ["oath"]

record

c

e

0

r

t

1

a

2

e

3

Result: ["oath","eat"]

reconstruct

Result: ["oath","eat"]

Key Takeaways

✓ Combining trie and backtracking efficiently prunes invalid search paths early.

This pruning is hard to see from code alone but is clear when watching trie traversal and cell marking.

✓ In-place marking of visited cells avoids extra space and prevents cycles during search.

Visualizing the board state changing clarifies how the algorithm avoids revisiting cells.

✓ Dynamic pruning of trie nodes after word discovery optimizes subsequent searches.

Seeing trie nodes removed after word found shows how the search space shrinks over time.

Practice

1. Given the following Python code snippet implementing the optimized trie approach, what is the output of maximizeXor(nums, queries) for nums = [0,1,2] and queries = [[3,1],[1,2]]?

class TrieNode:
    def __init__(self):
        self.children = [null, null]

class Trie:
    def __init__(self):
        self.root = TrieNode()

    def insert(self, num):
        node = self.root
        for i in range(31, -1, -1):
            bit = (num >> i) & 1
            if not node.children[bit]:
                node.children[bit] = TrieNode()
            node = node.children[bit]

    def maxXor(self, num):
        node = self.root
        if not node.children[0] and not node.children[1]:
            return -1
        max_xor = 0
        for i in range(31, -1, -1):
            bit = (num >> i) & 1
            toggled_bit = 1 - bit
            if node.children[toggled_bit]:
                max_xor |= (1 << i)
                node = node.children[toggled_bit]
            else:
                node = node.children[bit]
        return max_xor

def maximizeXor(nums, queries):
    nums.sort()
    queries = sorted([(x, m, i) for i, (x, m) in enumerate(queries)], key=lambda x: x[1])
    res = [-1] * len(queries)
    trie = Trie()
    idx = 0
    n = len(nums)
    for x, m, i in queries:
        while idx < n and nums[idx] <= m:
            trie.insert(nums[idx])
            idx += 1
        res[i] = trie.maxXor(x)
    return res

print(maximizeXor(nums, queries))

easy

A. [3, 3]

B. [2, 3]

C. [3, 1]

D. [-1, 3]

Solution

1. Step 1: Process first query (3,1)

   Only nums ≤ 1 are [0,1]. Insert 0 and 1 into trie. maxXor(3) with {0,1} is max(3^0=3,3^1=2)=3.

2. Step 2: Process second query (1,2)

   Now nums ≤ 2 are [0,1,2]. Insert 2. maxXor(1) with {0,1,2} is max(1^0=1,1^1=0,1^2=3)=3.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Results match expected XOR values [OK]

Hint: Insert nums ≤ m incrementally, then maxXor query [OK]

Common Mistakes:

• Forgetting to sort queries and nums
• Not inserting all eligible nums before query
• Returning -1 when trie is empty incorrectly

2. What is the worst-case time complexity of the optimal backtracking solution for the Expression Add Operators problem, given a numeric string of length n?

medium

A. O(n^3) due to nested loops and substring parsing

B. O(2^n) because each digit can either be concatenated or separated by an operator

C. O(4^n) because each digit can be followed by 4 choices: +, -, *, or no operator (concatenate)

D. O(3^n) since only three operators are inserted between digits

Solution

1. Step 1: Identify branching factor per digit

   At each digit (except the first), there are 4 choices: add '+', '-', '*', or concatenate (no operator).

2. Step 2: Calculate total combinations

   With n digits, the number of expressions is roughly 4^(n-1), which is O(4^n) in worst case.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   4 choices per digit lead to exponential 4^n growth [OK]

Hint: Count operator choices plus concatenation per digit [OK]

Common Mistakes:

• Confusing 3 operators only, ignoring concatenation
• Assuming polynomial complexity

3. Examine the following buggy code snippet for the optimized trie approach. Which line contains the subtle bug that can cause incorrect results or runtime errors when no elements in nums are less than or equal to m in a query?

class TrieNode:
    def __init__(self):
        self.children = [null, null]

class Trie:
    def __init__(self):
        self.root = TrieNode()

    def insert(self, num):
        node = self.root
        for i in range(31, -1, -1):
            bit = (num >> i) & 1
            if not node.children[bit]:
                node.children[bit] = TrieNode()
            node = node.children[bit]

    def maxXor(self, num):
        node = self.root
        # Bug: missing check for empty trie
        max_xor = 0
        for i in range(31, -1, -1):
            bit = (num >> i) & 1
            toggled_bit = 1 - bit
            if node.children[toggled_bit]:
                max_xor |= (1 << i)
                node = node.children[toggled_bit]
            else:
                node = node.children[bit]
        return max_xor

# rest of code omitted for brevity

medium

A. Line missing check if trie is empty before traversal in maxXor

B. Line 'if not node.children[bit]: node.children[bit] = TrieNode()' in insert method

C. Line with 'node = self.root' in maxXor method

D. Line 'node = node.children[bit]' in else branch of maxXor

Solution

1. Step 1: Identify missing empty trie check

   maxXor should return -1 if trie is empty (no children at root), but this check is missing.

2. Step 2: Consequence of missing check

   Without this, traversal accesses null children causing runtime error or incorrect results when no nums ≤ m.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Adding 'if not node.children[0] and not node.children[1]: return -1' fixes bug [OK]

Hint: Always check if trie is empty before querying [OK]

Common Mistakes:

• Forgetting empty trie check
• Incorrect bit indexing
• Misplaced node updates

4. What is the time complexity of the optimal binary search partition approach to find the median of two sorted arrays of sizes m and n (m ≤ n)?

medium

A. O(log(min(m, n)))

B. O(m + n)

C. O(log(m + n))

D. O(log(m))

Solution

1. Step 1: Identify which array is binary searched

   The algorithm always binary searches the smaller array of size m.

2. Step 2: Analyze binary search complexity

   Binary search on array of size m takes O(log m) time. Since m ≤ n, this is O(log(min(m, n))).

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Binary search on smaller array yields O(log(min(m,n))) [OK]

Hint: Binary search on smaller array size defines complexity [OK]

Common Mistakes:

• Assuming O(m + n) due to merging intuition
• Confusing log(m + n) with log(min(m, n))
• Ignoring that binary search is only on smaller array

5. Suppose the Alien Dictionary problem is extended so that words can be repeated multiple times in the input list, possibly introducing duplicate edges. Which modification to the optimal Kahn's algorithm approach correctly handles this scenario without corrupting the in-degree counts?

hard

A. Use a set to track edges and only add an edge and increment in-degree if it is not already present

B. Reset in-degree counts after building the graph to avoid duplicates

C. Remove the edge deduplication check and increment in-degree for every edge found

D. Use DFS instead of BFS to avoid counting duplicate edges

Solution

1. Step 1: Identify problem with duplicate edges

   Repeated words can cause multiple identical edges, inflating in-degree counts incorrectly.

2. Step 2: Use edge deduplication to prevent multiple increments

   Track edges in a set and only add/increment if edge is new, preserving correct in-degree.

3. Step 3: Confirm BFS with correct in-degree works properly

   Maintains accurate topological order and cycle detection despite duplicates.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Edge deduplication is essential for correctness with repeated words [OK]

Hint: Avoid incrementing in-degree multiple times for same edge [OK]

Common Mistakes:

• Ignoring duplicates
• Resetting in-degree incorrectly
• Switching to DFS unnecessarily