Word Break (Trie Approach)

▶

Steps

setup

Initialize Trie Root

Create the root node of the trie, which is initially empty with no children and not marking any word end.

💡 The root node is the starting point for all insertions and searches in the trie.

Line:

root = TrieNode()

💡 Understanding the root node as the base of the trie structure is essential before inserting any words.

insert

Insert reversed word 'leet' into trie - char 't'

Start inserting the word 'leet' in reverse order. Insert the first character 't' as a child of the root node.

💡 Inserting reversed words allows efficient backward substring matching during DP.

Line:

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

💡 Each new character creates a new node if not already present, building the trie structure.

insert

Insert reversed word 'leet' into trie - char 'e'

Insert the next character 'e' of the reversed word 'leet' as a child of node 't'.

💡 Continuing insertion builds the path representing the reversed word.

Line:

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

💡 The trie path grows deeper with each character inserted.

insert

Insert reversed word 'leet' into trie - char 'e' (second 'e')

Insert the next character 'e' (second 'e' in 'leet') as a child of the previous 'e' node.

💡 Repeated characters are inserted as separate nodes along the path.

Line:

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

💡 Trie nodes represent characters in sequence, even if repeated.

insert

Insert reversed word 'leet' into trie - char 'l' and mark end

Insert the last character 'l' of the reversed word 'leet' and mark this node as end of word.

💡 Marking end_of_word signals a complete dictionary word in the trie.

Line:

if ch not in node.children:
  node.children[ch] = TrieNode()
node = node.children[ch]
node.is_word = True

💡 End of word nodes allow the algorithm to detect valid dictionary words during search.

insert

Insert reversed word 'code' into trie - char 'e'

Start inserting the second dictionary word 'code' in reverse order. Insert 'e' as a child of root. Since 'e' is not a child of root, create a new node.

💡 Inserting multiple words builds a trie with shared prefixes where possible.

Line:

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

💡 Trie branches grow for different word suffixes starting from root.

insert

Insert reversed word 'code' into trie - char 'd'

Insert the next character 'd' as a child of 'e' node for the reversed word 'code'.

💡 Continuing insertion builds the reversed word path in the trie.

Line:

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

💡 Trie nodes represent characters in sequence for each reversed word.

insert

Insert reversed word 'code' into trie - char 'o'

Insert the next character 'o' as a child of 'd' node.

💡 Building the reversed word path continues character by character.

Line:

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

💡 Trie paths represent reversed dictionary words for efficient backward matching.

insert

Insert reversed word 'code' into trie - char 'c' and mark end

Insert the last character 'c' of the reversed word 'code' and mark this node as end of word.

💡 Marking end_of_word nodes allows the search to identify complete dictionary words.

Line:

if ch not in node.children:
  node.children[ch] = TrieNode()
node = node.children[ch]
node.is_word = True

💡 The trie now fully represents both dictionary words in reversed form.

setup

Initialize DP array with dp[0] = True

Create a dp array of length n+1 (9) with all False except dp[0] set to True, representing empty string segmentation.

💡 dp[i] indicates if s[:i] can be segmented into dictionary words.

Line:

dp = [False] * (n + 1)
dp[0] = True

💡 Starting with dp[0] = True allows building solutions for longer prefixes.

search

Check substring ending at i=4 ('leet')

Start checking substrings ending at index 4. Traverse backwards from j=3 to 0 matching characters in trie reversed order.

💡 We try to find a dictionary word ending at position i by matching backwards in the trie.

Line:

for i in range(1, n + 1):
  node = root
  for j in range(i - 1, -1, -1):
    ch = s[j]
    if ch not in node.children:
      break
    node = node.children[ch]
    if node.is_word and dp[j]:
      dp[i] = True
      break

💡 Matching backwards in trie corresponds to checking suffixes of s[:i].

compare

Match character 't' at s[3]

Check if character 't' at s[3] exists as child of root. It does, move to node 't'.

💡 Matching last character of substring in reversed trie is first step.

Line:

if ch not in node.children:
  break
node = node.children[ch]

💡 Trie traversal follows characters backwards in s.

compare

Match character 'e' at s[2]

Check if character 'e' at s[2] exists as child of node 't'. It does, move to node 'e'.

💡 Continuing backward matching in trie.

Line:

if ch not in node.children:
  break
node = node.children[ch]

💡 Matching continues along trie path for reversed substring.

compare

Match character 'e' at s[1]

Check if character 'e' at s[1] exists as child of node 'e'. It does, move to next node 'e'.

💡 Continuing backward matching in trie.

Line:

if ch not in node.children:
  break
node = node.children[ch]

💡 Trie path matches substring s[1:4] reversed.

compare

Match character 'l' at s[0] and find word end

Check if character 'l' at s[0] exists as child of node 'e'. It does, move to node 'l' which marks end_of_word.

💡 Finding end_of_word means substring s[0:4] is a dictionary word reversed.

Line:

if ch not in node.children:
  break
node = node.children[ch]
if node.is_word and dp[j]:
  dp[i] = True
  break

💡 Substring 'leet' can be segmented, dp updated accordingly.

search

Check substring ending at i=8 ('leetcode')

Now check substrings ending at index 8. Traverse backwards from j=7 to 0 matching characters in trie reversed order.

💡 We try to find a dictionary word ending at position 8 by matching backwards in the trie.

Line:

for i in range(1, n + 1):
  node = root
  for j in range(i - 1, -1, -1):
    ch = s[j]
    if ch not in node.children:
      break
    node = node.children[ch]
    if node.is_word and dp[j]:
      dp[i] = True
      break

💡 Matching backwards in trie corresponds to checking suffixes of s[:8].

compare

Match character 'e' at s[7]

Check if character 'e' at s[7] exists as child of root. It does, move to node 'e'.

💡 Matching last character of substring in reversed trie is first step.

Line:

if ch not in node.children:
  break
node = node.children[ch]

💡 Trie traversal follows characters backwards in s.

compare

Match character 'd' at s[6]

Check if character 'd' at s[6] exists as child of node 'e'. It does, move to node 'd'.

💡 Continuing backward matching in trie.

Line:

if ch not in node.children:
  break
node = node.children[ch]

💡 Matching continues along trie path for reversed substring.

compare

Match character 'o' at s[5]

Check if character 'o' at s[5] exists as child of node 'd'. It does, move to node 'o'.

💡 Continuing backward matching in trie.

Line:

if ch not in node.children:
  break
node = node.children[ch]

💡 Trie path matches substring s[5:8] reversed.

compare

Match character 'c' at s[4] and find word end

Check if character 'c' at s[4] exists as child of node 'o'. It does, move to node 'c' which marks end_of_word.

💡 Finding end_of_word means substring s[4:8] is a dictionary word reversed.

Line:

if ch not in node.children:
  break
node = node.children[ch]
if node.is_word and dp[j]:
  dp[i] = True
  break

💡 Substring 'code' can be segmented, dp updated accordingly.

reconstruct

Return final answer dp[len(s)]

Return dp[8] which is True, indicating the input string can be segmented into dictionary words.

💡 The final dp value confirms the segmentation possibility.

Line:

return dp[n]

💡 The algorithm successfully segmented 'leetcode' as 'leet' + 'code'.

class TrieNode:
    def __init__(self):
        self.children = {}
        self.is_word = False

class Solution:
    def buildTrie(self, words):
        root = TrieNode()  # STEP 1
        for word in words:
            node = root
            for ch in reversed(word):  # STEP 2-9
                if ch not in node.children:
                    node.children[ch] = TrieNode()
                node = node.children[ch]
            node.is_word = True
        return root

    def wordBreak(self, s, wordDict):
        root = self.buildTrie(wordDict)  # STEP 1-9
        n = len(s)
        dp = [False] * (n + 1)  # STEP 10
        dp[0] = True

        for i in range(1, n + 1):  # STEP 11-20
            node = root
            for j in range(i - 1, -1, -1):
                ch = s[j]
                if ch not in node.children:
                    break
                node = node.children[ch]
                if node.is_word and dp[j]:
                    dp[i] = True
                    break
        return dp[n]  # STEP 21

if __name__ == '__main__':
    sol = Solution()
    print(sol.wordBreak("leetcode", ["leet", "code"]))  # True

📊

Word Break (Trie Approach) - Watch the Algorithm Execute, Step by Step

Watching this step-by-step visualization reveals the interplay between trie prefix matching and dynamic programming, making the segmentation logic intuitive.

insert

insert

leet

t

insert

leet

te

insert

leet

ee

insert

leet

el*

insert

code

e

insert

code

ed

insert

code

do

insert

code

oc*

search

search

leetcode

t

search

leetcode

te

search

leetcode

ee

search

leetcode

el*

search

leetcode

l*

search

leetcode

e

search

leetcode

ed

search

leetcode

do

search

leetcode

oc*

search

leetcode

c*

search

Key Takeaways

✓ Building the trie with reversed dictionary words enables efficient backward substring matching.

This insight is hard to see from code alone because the reversal and its impact on search direction are subtle.

✓ The dp array stores segmentation feasibility up to each index, updated only when a valid dictionary word is found ending at that index.

Visualizing dp updates alongside trie traversal clarifies the dynamic programming dependency.

✓ The search breaks early when a character mismatch occurs or a valid segmentation is found, optimizing the algorithm.

Seeing the early break decisions in the trie traversal helps understand the pruning of unnecessary checks.

Practice

1. You are given a list of words and need to find the longest word such that every prefix of the word is also in the list. Which approach guarantees an optimal solution for this problem?

easy

A. Sort the words by length and lex order, then check prefixes using a hash set.

B. Apply a greedy approach by always choosing the lexicographically smallest prefix at each step.

C. Use dynamic programming to build the longest word by extending smaller valid words.

D. Build a trie from the words and perform a BFS traversal to find the longest valid word.

Solution

1. Step 1: Understand the prefix condition

   The problem requires that every prefix of the candidate word must be present in the list, which naturally fits a trie structure where each node represents a prefix.

2. Step 2: Why BFS on trie works best

   BFS traversal on the trie allows level-by-level exploration, ensuring that only nodes representing complete words are considered, thus guaranteeing the longest word with all prefixes present is found efficiently.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Trie + BFS directly encodes prefix checks and finds longest word [OK]

Hint: Trie BFS ensures prefix validity and longest word [OK]

Common Mistakes:

• Assuming greedy lex order always works
• Using DP without prefix structure
• Checking prefixes inefficiently without trie

2. Examine the following buggy search method for the WordDictionary implemented with a trie. Which line contains the subtle bug that causes incorrect search results for patterns with '.' wildcard?

def search(self, word: str) -> bool:
    stack = [(0, self.root)]
    while stack:
        index, node = stack.pop()
        if index == len(word):
            if node.is_end:
                return True
            continue
        ch = word[index]
        if ch == '.':
            for child in node.children:
                stack.append((index + 1, child))
        else:
            if ch in node.children:
                stack.append((index + 1, node.children[ch]))
    return False

medium

A. Line with 'stack = [(0, self.root)]'

B. Line with 'for child in node.children:'

C. Line with 'if node.is_end:'

D. Line with 'if ch in node.children:'

Solution

1. Step 1: Identify how children are iterated for '.' wildcard

   The code uses 'for child in node.children:', which iterates over keys (characters), not child nodes.

2. Step 2: Understand impact of iterating keys instead of nodes

   Appending keys instead of TrieNode objects causes incorrect stack entries and search failure.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Must iterate over node.children.values() to get child nodes [OK]

Hint: Iterate node.children.values(), not keys [OK]

Common Mistakes:

• Iterating keys instead of child nodes
• Forgetting to mark is_end
• Misplacing base case check

3. What is the time complexity of the optimal trie + BFS approach for finding the longest word in a dictionary with n words, each of average length m?

medium

A. O(n * m + n * 26) because building trie takes O(n*m) and BFS visits each node once

B. O(n * m * 26) since BFS explores all children for each character

C. O(n * m^2) due to checking all prefixes for each word

D. O(n * m log n) due to sorting children at each node during BFS

Solution

1. Step 1: Analyze trie construction

   Inserting n words of length m takes O(n * m) time as each character is processed once.

2. Step 2: Analyze BFS traversal

   BFS visits each node once; each node has up to 26 children, so total BFS cost is O(n * 26) which is O(n).

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Trie build + BFS traversal sum to O(n*m + n*26) [OK]

Hint: Trie build O(n*m), BFS O(n*26) combined [OK]

Common Mistakes:

• Confusing BFS cost as O(n*m*26)
• Forgetting BFS visits each node once
• Assuming sorting children adds log factor per node

4. The following code attempts to answer maximum XOR queries with constraints using a bit trie. Which line contains a subtle bug that can cause incorrect results or runtime errors when no nums ≤ m are available?

medium

A. Line: node = node.children[bit]

B. Line: if not node.children[bit]: node.children[bit] = TrieNode()

C. Line: node = self.root

D. Line: if node.children[toggled_bit]:

Solution

1. Step 1: Identify empty trie scenario

   If no nums ≤ m, trie is empty; node.children[bit] can be None.

2. Step 2: Check max_xor traversal

   Line assigning node = node.children[bit] assumes child exists, causing runtime error or wrong result.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Must handle empty child case to avoid errors [OK]

Hint: Check for None before descending trie [OK]

Common Mistakes:

• Ignoring empty trie case
• Assuming children always exist
• Not returning -1 when no valid nums

5. What is the time complexity of building the trie and retrieving suggestions for a searchWord of length m, given n products each of average length k, when using the trie with stored top 3 suggestions approach?

medium

A. O(m * n * k) because each prefix requires scanning all products

B. O(n * k * m) because for each character in searchWord, we traverse all products

C. O(n * k + m) because building the trie takes O(n * k) and searching takes O(m)

D. O(n + m * k) because building trie is linear in n and searching depends on k

Solution

1. Step 1: Analyze trie building complexity

   Building the trie requires inserting each of the n products of length k, so O(n * k).

2. Step 2: Analyze search complexity

   Searching for suggestions for each of the m characters in searchWord requires traversing down the trie nodes, O(m).

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Trie building dominates with O(n*k), search is O(m) [OK]

Hint: Trie build is O(n*k), search is O(m) [OK]

Common Mistakes:

• Confusing brute force with trie complexity
• Multiplying m unnecessarily
• Ignoring that search is prefix traversal only