Word Search II (Multiple Words in Grid)

▶

Steps

setup

Initialize Trie Root

Create the root node of the trie, which is empty initially and will serve as the starting point for inserting all words.

💡 The root node is the foundation of the trie; all words will branch out from here.

Line:

root = TrieNode()

💡 The trie starts empty and will grow as words are inserted character by character.

insert

Insert Word 'oath' - Insert 'o'

Start inserting the first word 'oath' into the trie by adding a child node for the character 'o' under the root.

💡 Inserting the first character creates a new branch in the trie for this word.

Line:

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

💡 Each new character not already in the trie creates a new node, expanding the trie structure.

insert

Insert Word 'oath' - Insert 'a'

Continue inserting 'oath' by adding a child node for 'a' under the 'o' node.

💡 Each character extends the path deeper into the trie, representing the word's prefix.

Line:

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

💡 The trie grows deeper as more characters are inserted for the current word.

insert

Insert Word 'oath' - Insert 't' and 'h' and Mark End

Insert 't' and 'h' nodes sequentially under 'a', then mark the last node as end_of_word for 'oath'.

💡 Marking the end of a word allows the trie to recognize complete words during search.

Line:

node.word = w

💡 The trie now contains a full path representing 'oath' with a terminal node indicating word completion.

insert

Insert Word 'pea' - Insert 'p', 'e', 'a'

Insert the word 'pea' by creating new nodes for 'p', 'e', and 'a' under the root, marking the last node as end_of_word.

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

Line:

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

💡 The trie branches out to accommodate words with different starting letters.

insert

Insert Word 'eat' - Insert 'e', 'a', 't'

Insert 'eat' by creating nodes for 'e', 'a', and 't' under the root, marking the last node as end_of_word.

💡 Words sharing no prefix with existing branches add new branches at the root.

Line:

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

💡 The trie now has three branches for the three distinct starting letters 'o', 'p', and 'e'.

insert

Insert Word 'rain' - Insert 'r', 'a', 'i', 'n'

Insert 'rain' by creating nodes for 'r', 'a', 'i', and 'n' under the root, marking the last node as end_of_word.

💡 Each new word adds a unique path if no prefix is shared.

Line:

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

💡 The trie now fully represents all input words with separate branches for distinct prefixes.

traverse

Start DFS from Board Cell (0,0) 'o'

Begin DFS from board cell (0,0) containing 'o', matching it with the root's child 'o' in the trie.

💡 DFS explores board cells matching trie children to find words.

Line:

char = board[r][c]
if char == '#' or char not in node.children:
    return
node = node.children[char]

💡 DFS prunes paths early if the board character does not match any trie child.

traverse

DFS Explore from (0,1) 'a' under 'o'

From 'o' node, DFS moves to adjacent board cell (0,1) with 'a', matching the 'a' child of 'o' in the trie.

💡 DFS follows trie edges matching board characters to build words.

Line:

node = node.children[char]

💡 Matching characters on board and trie nodes extend the search path.

traverse

DFS Explore from (1,1) 't' under 'a'

DFS moves to board cell (1,1) with 't', matching the 't' child of 'a' node in the trie.

💡 Following the trie path character by character on the board is how words are found.

Line:

node = node.children[char]

💡 The search path is extending deeper into the trie and board simultaneously.

traverse

DFS Explore from (2,1) 'h' under 't' and Find Word 'oath'

DFS moves to board cell (2,1) with 'h', matching the 'h' child of 't' node. This node marks the end of word 'oath', so the word is found and added to results.

💡 Finding a node with a word means a complete word is matched on the board.

Line:

if node.word:
    result.append(node.word)
    node.word = None

💡 The algorithm detects complete words during DFS and prevents duplicate findings.

traverse

DFS Backtrack and Explore from (1,0) 'e' for Word 'eat'

After backtracking, DFS starts from board cell (1,0) with 'e', matching the 'e' child of root in the trie to search for 'eat'.

💡 DFS explores all board cells as potential word starts.

Line:

if char not in node.children:
    return
node = node.children[char]

💡 The search restarts from new board positions to find other words.

traverse

DFS Explore from (1,2) 'a' under 'e'

DFS moves to board cell (1,2) with 'a', matching the 'a' child of 'e' node in the trie.

💡 Continuing to match characters on the board with trie nodes extends the search path.

Line:

node = node.children[char]

💡 The search path is building towards a complete word.

traverse

DFS Explore from (1,1) 't' under 'a' and Find Word 'eat'

DFS moves to board cell (1,1) with 't', matching the 't' child of 'a' node. This node marks the end of word 'eat', so the word is found and added to results.

💡 Detecting end_of_word nodes during DFS means a word is found on the board.

Line:

if node.word:
    result.append(node.word)
    node.word = None

💡 The algorithm successfully finds multiple words by traversing different trie branches.

traverse

DFS Attempts on 'pea' and 'rain' Fail

DFS explores board cells for 'p' and 'r' but fails to find complete paths matching 'pea' and 'rain' in the trie.

💡 DFS prunes paths early when board characters do not match trie children.

Line:

if char == '#' or char not in node.children:
    return

💡 The trie structure helps prune impossible paths quickly, improving efficiency.

reconstruct

Final Result: Words Found 'eat' and 'oath'

After completing DFS from all board cells, the algorithm returns the list of found words: 'eat' and 'oath'.

💡 The final output contains only words that can be formed by adjacent letters on the board.

Line:

return result

💡 The trie and DFS combination efficiently finds all valid words in the board.

from typing import List

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

class Solution:
    def buildTrie(self, words):
        root = TrieNode()  # STEP 1
        for w in words:  # STEP 2-7
            node = root
            for c in w:
                if c not in node.children:
                    node.children[c] = TrieNode()  # STEP 2-7
                node = node.children[c]
            node.word = w  # STEP 4,7
        return root

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

        def dfs(r, c, node):
            if r < 0 or r >= rows or c < 0 or c >= cols:  # STEP 8-15
                return
            char = board[r][c]
            if char == '#' or char not in node.children:
                return
            node = node.children[char]  # STEP 8-15
            if node.word:
                result.append(node.word)  # STEP 11,14
                node.word = None  # avoid duplicates
            board[r][c] = '#'
            for dr, dc in [(1,0),(-1,0),(0,1),(0,-1)]:
                dfs(r+dr, c+dc, node)
            board[r][c] = char

        for r in range(rows):  # STEP 8-15
            for c in range(cols):
                dfs(r, c, root)
        return result  # STEP 16

📊

Word Search II (Multiple Words in Grid) - Watch the Algorithm Execute, Step by Step

Watching the algorithm step-by-step reveals how the trie efficiently encodes the word list and how DFS explores the board while pruning unnecessary paths, which is difficult to grasp from code alone.

insert

insert

oath

o

insert

oath

oa

insert

oath

oath*

insert

pea

pea*

insert

eat

eat*

insert

rain

rain*

search

o

search

oa

search

at

search

th*

search

e

search

ea

search

at*

search

search

Key Takeaways

✓ The trie efficiently encodes all words, allowing the DFS to prune invalid paths early.

Without visualization, it's hard to see how the trie structure prevents unnecessary searches on the board.

✓ DFS explores the board by matching characters to trie nodes, building active paths that represent prefixes of words.

Seeing the active path helps understand how partial matches lead to full word discoveries.

✓ When a word is found, it is recorded and removed from the trie node to avoid duplicates, demonstrating in-place pruning.

This step is subtle in code but critical for efficiency and correctness, and visualization makes it clear.

Practice

1. You need to design a data structure that supports inserting key-value pairs and efficiently returning the sum of all values of keys that start with a given prefix. Which approach guarantees the most optimal time complexity for both insert and sum operations?

easy

A. Use a hash map to store all keys and values, and scan all keys on each sum query to accumulate matching prefixes.

B. Use a dynamic programming approach to precompute sums for all possible prefixes and update them on each insert.

C. Use a balanced binary search tree keyed by strings, and perform range queries for prefix sums.

D. Use a trie where each node stores the cumulative sum of all keys passing through it, updating sums on insert and traversing prefix nodes on sum queries.

Solution

1. Step 1: Understand the problem requirements

   The data structure must support fast insertions and prefix sum queries.

2. Step 2: Evaluate approaches

   Hash map with scanning is O(n*k) per sum, which is inefficient. Balanced BST range queries are complex and slower. DP precomputation is infeasible for dynamic inserts. Trie with prefix sums allows O(k) insert and sum operations.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Trie prefix sums enable O(k) operations [OK]

Hint: Trie with prefix sums supports O(k) insert and sum [OK]

Common Mistakes:

• Thinking brute force scanning is efficient enough
• Using BSTs for prefix sums
• Trying DP precomputation for dynamic keys

2. Consider the following code snippet implementing the optimal Word Break solution using a reversed trie and iterative DP. Given s = "leetcode" and wordDict = ["leet", "code"], what is the value of dp[8] after the loop completes?

easy

A. False

B. Raises an exception

C. None

D. True

Solution

1. Step 1: Trace dp array updates for s="leetcode"

   dp[0] = True initially. For i=4, substring s[0:4] = "leet" is in dictionary, so dp[4] = True. For i=8, substring s[4:8] = "code" is in dictionary and dp[4] is True, so dp[8] = True.

2. Step 2: Confirm final dp[n] value

   Since the entire string can be segmented, dp[8] = True.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   dp correctly marks segmentable prefixes [OK]

Hint: dp[i] true if prefix s[:i] can be segmented [OK]

Common Mistakes:

• Off-by-one errors in dp indexing
• Not breaking early when dp[i] is true
• Confusing reversed trie traversal

3. What is the time complexity of the optimal bitwise trie approach to count pairs with XOR in a range for an input array of size n and maximum number M (max element)?

medium

A. O(n * log M)

B. O(n^2)

C. O(n * M)

D. O(n * log n)

Solution

1. Step 1: Identify operations per element

   Each number is inserted into the trie in O(log M) time, where M is the max number (bit length).

2. Step 2: Query per element also takes O(log M)

   For each number, querying the trie for counts less than a limit also takes O(log M).

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Overall complexity is O(n * log M) due to insert and query per element [OK]

Hint: Trie operations scale with bit length, not array size squared [OK]

Common Mistakes:

• Assuming O(n^2) due to pairs
• Confusing M with n in complexity
• Ignoring log factor from bit length

4. Consider the following buggy Trie insert method. Which line contains the subtle bug that causes search to fail for inserted words?

medium

A. Line where node = self.root is assigned

B. Line where node = node.children[ch] is assigned inside the loop

C. Line where isEnd flag should be set but is missing

D. Line where the if condition checks if ch not in node.children

Solution

1. Step 1: Identify missing isEnd flag set

   After inserting all characters, isEnd must be set true to mark word end. This line is missing.

2. Step 2: Understand impact on search

   Without isEnd=true, search returns false even if path exists, because node.isEnd remains false.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Missing isEnd assignment causes search failure for inserted words [OK]

Hint: isEnd must be set after inserting entire word [OK]

Common Mistakes:

• Forgetting to mark isEnd after insertion

5. Suppose the problem is modified so that words can be reused multiple times to form longer words (e.g., prefixes can be repeated). Which modification to the trie + BFS approach correctly handles this variant?

hard

A. No change needed; the existing BFS approach already handles reuse of words.

B. Modify BFS to enqueue child nodes even if child.word is None, allowing repeated prefixes.

C. Use DFS with memoization to explore repeated prefixes and avoid cycles.

D. Replace trie with a graph where edges represent possible concatenations and run BFS.

Solution

1. Step 1: Understand reuse of words

   Allowing reuse means prefixes can be repeated multiple times, potentially causing cycles in traversal.

2. Step 2: Why DFS with memoization is needed

   DFS with memoization prevents infinite loops by caching results for nodes, correctly handling repeated prefixes and cycles.

3. Step 3: Why other options fail

   Existing BFS assumes no reuse; enqueuing nodes without word breaks prefix condition; graph BFS without cycle handling risks infinite loops.

4. Final Answer:

   Option C -> Option C

5. Quick Check:

   DFS + memoization handles repeated prefixes safely [OK]

Hint: Reuse requires cycle-safe DFS with memoization [OK]

Common Mistakes:

• Assuming BFS handles reuse without changes
• Enqueueing invalid nodes breaks prefix rules
• Ignoring cycles in graph representation