Concatenated Words

▶

Steps

setup

Initialize Trie Root

Create the root node of the trie, which is empty and has no children or word end marker.

💡 The root node is the starting point for all word insertions and searches, representing an empty prefix.

Line:

root = TrieNode()

💡 The trie starts empty, ready to build from the input words.

insert

Insert 'cat' - Insert 'c'

Start inserting the word 'cat'. Insert 'c' as a child of root since it does not exist yet.

💡 Inserting characters creates new nodes for prefixes not yet in the trie.

Line:

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

💡 New branches are created for new prefixes, expanding the trie.

insert

Insert 'cat' - Insert 'a'

Continue inserting 'cat'. Insert 'a' as a child of 'c' node since it does not exist yet.

💡 Each character extends the current prefix path in the trie.

Line:

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

💡 Trie nodes form chains representing word prefixes.

insert

Insert 'cat' - Insert 't' and mark end

Insert 't' as a child of 'a' node and mark this node as end of word for 'cat'.

💡 Marking end_of_word signals a complete word in the trie.

Line:

node.is_word = True

💡 End markers allow recognizing complete words during search.

insert

Insert 'cats' - Reuse prefix 'cat', insert 's'

Insert 'cats'. Reuse existing nodes for 'c', 'a', 't'. Insert new node 's' as child of 't' and mark end.

💡 Trie shares common prefixes to save space and speed up searches.

Line:

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

💡 Common prefixes are stored once, enabling efficient prefix checks.

traverse

Start DFS on 'catsdogcats' from index 0

Begin DFS to check if 'catsdogcats' can be formed by concatenation. Start at index 0 with root node.

💡 DFS explores prefixes in trie to find valid word segments.

Line:

def dfs(word, start):
    if start == len(word):
        return True
    node = root

💡 DFS tries to segment the word starting from the beginning.

traverse

DFS: Traverse prefix 'cats' in trie

Traverse characters 'c', 'a', 't', 's' in trie. At 's', a word end is found for 'cats'.

💡 Finding a word end means a valid prefix segment is found.

Line:

if node.is_word:
    if dfs(word, i + 1):
        return True

💡 DFS breaks the word into prefix + suffix and checks suffix recursively.

traverse

DFS: Recurse on suffix 'dogcats' from index 4

Start DFS from index 4 to check if suffix 'dogcats' can be segmented.

💡 DFS restarts from root to find prefixes in the suffix.

Line:

return dfs(word, i + 1)

💡 The problem reduces to checking if suffix is concatenated word.

traverse

DFS: Traverse prefix 'dog' in trie from index 4

Traverse 'd', 'o', 'g' in trie. At 'g', word end found for 'dog'.

💡 Finding another word end allows further suffix checks.

Line:

if node.is_word:
    if dfs(word, i + 1):
        return True

💡 DFS continues to break suffix into smaller words.

traverse

DFS: Recurse on suffix 'cats' from index 7

Start DFS from index 7 to check if suffix 'cats' can be segmented.

💡 DFS tries to segment the remaining suffix recursively.

Line:

return dfs(word, i + 1)

💡 The suffix 'cats' is checked similarly to the prefix.

traverse

DFS: Traverse prefix 'cats' in trie from index 7

Traverse 'c', 'a', 't', 's' again. At 's', word end found for 'cats'.

💡 Finding word end at suffix confirms full segmentation.

Line:

if node.is_word:
    if dfs(word, i + 1):
        return True

💡 Complete segmentation found, confirming concatenated word.

prune

Mark 'catsdogcats' as concatenated word

Since DFS returned True, 'catsdogcats' is added to the result list.

💡 Words that can be segmented into smaller words are concatenated words.

Line:

if dfs(word, 0):
    result.append(word)

💡 The algorithm successfully identifies concatenated words.

traverse

Repeat DFS for 'dogcatsdog' and find concatenation

Perform DFS on 'dogcatsdog' similarly, finding valid prefixes 'dog', 'cats', and 'dog' again.

💡 The algorithm applies the same logic to all words to find concatenations.

Line:

memo.clear()
node.is_word = False
if dfs(word, 0):
    result.append(word)

💡 Concatenated words can be formed by multiple smaller words in trie.

traverse

Repeat DFS for 'ratcatdogcat' and find concatenation

DFS confirms 'ratcatdogcat' is concatenated from 'rat', 'cat', 'dog', and 'cat'.

💡 Multiple concatenated words are found by the same process.

Line:

memo.clear()
node.is_word = False
if dfs(word, 0):
    result.append(word)

💡 The algorithm generalizes to all words in the input.

reconstruct

Final Result: Concatenated Words Found

The algorithm outputs the list of concatenated words found: ['catsdogcats', 'dogcatsdog', 'ratcatdogcat'].

💡 The final answer is the collection of all words confirmed as concatenated.

Line:

return result

💡 The trie and DFS approach efficiently identifies concatenated words.

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

class Solution:
    def findAllConcatenatedWordsInADict(self, words):
        root = TrieNode()  # STEP 1

        def insert(word):  # STEP 2-5
            node = root
            for ch in word:
                if ch not in node.children:
                    node.children[ch] = TrieNode()  # STEP insert node
                node = node.children[ch]
            node.is_word = True  # STEP mark end

        for word in words:
            if word:
                insert(word)  # STEP insert all words

        memo = {}

        def dfs(word, start):  # STEP 6-11
            if start == len(word):
                return True
            if start in memo:
                return memo[start]
            node = root
            for i in range(start, len(word)):
                ch = word[i]
                if ch not in node.children:
                    break
                node = node.children[ch]
                if node.is_word:
                    if dfs(word, i + 1):
                        memo[start] = True
                        return True
            memo[start] = False
            return False

        result = []
        for word in words:
            if not word:
                continue
            memo.clear()
            node = root
            for ch in word:
                node = node.children[ch]
            node.is_word = False  # Temporarily disable to avoid self-count
            if dfs(word, 0):  # STEP DFS check
                result.append(word)  # STEP add to result
            node.is_word = True  # Restore
        return result  # STEP final return

📊

Concatenated Words - Watch the Algorithm Execute, Step by Step

Watching each step of trie construction and DFS traversal reveals how the algorithm efficiently finds concatenated words by reusing prefix information and pruning redundant searches.

insert

insert

cat

c

insert

cat

ca

insert

cat

cat*

insert

cats

cat*s*

search

catsdogcats

cat*s*dog*hipporat*

search

catsdogcats

cat*s*

search

catsdogcats

dog*

search

catsdogcats

dog*

search

catsdogcats

cat*s*

search

catsdogcats

cat*s*

Search: true

search

cat*s*dog*hipporat*

search

dogcatsdog

Search: true

search

ratcatdogcat

Search: true

search

cat*s*dog*hipporat*

Key Takeaways

✓ Trie structure efficiently stores all words sharing prefixes, enabling fast prefix checks during DFS.

This is hard to see from code alone because the trie structure is implicit; visualization shows how nodes and edges represent prefixes.

✓ DFS with memoization breaks down the concatenation problem into smaller subproblems, avoiding repeated work.

Memoization's effect is subtle in code but clear in visualization as repeated indices are skipped.

✓ Temporarily disabling the current word's end marker prevents counting the word itself as a concatenation, ensuring correctness.

This subtle trick is easy to miss in code but critical for correct results, and visualization highlights this step.

Practice

1. Given the following code snippet implementing the optimal trie-based solution, what is the output of replaceWords(['cat', 'bat', 'rat'], 'the cattle was rattled by the battery')?

easy

A. the cat was rat by the battery

B. the cat was rat by the bat

C. the cattle was rat by the battery

D. the cat was rattled by the battery

Solution

1. Step 1: Trace prefix search for 'cattle'

   Check 'c' -> 'a' -> 't' in trie; 'cat' is a root and shortest prefix, so replace 'cattle' with 'cat'.

2. Step 2: Trace prefix search for 'rattled' and 'battery'

   'rattled' matches 'rat' prefix; 'battery' matches 'bat' prefix. Other words have no prefix match and remain unchanged.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   All replaced words correspond to shortest root prefixes [OK]

Hint: Shortest prefix found stops search early [OK]

Common Mistakes:

• Replacing with longer prefix
• Not replacing words without prefix

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-based solution to replace words in a sentence, where m is the number of words in the sentence and k is the average length of each word, assuming the trie is already built from n root words with average length l?

medium

A. O(n * l + m * k) because building the trie takes O(n * l) and searching each word takes O(k)

B. O(m * k) because each word is searched character by character in the trie until a prefix is found or word ends

C. O(m * k * l) because for each word, the trie traversal depends on both word and root lengths

D. O(m * n * l) because each word is compared against all roots in the trie

Solution

1. Step 1: Identify trie construction cost

   Building the trie from n roots each of length l takes O(n * l) time.

2. Step 2: Identify search cost per word

   Searching each of the m words of length k in the trie takes O(k) time per word.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Sum of build and search times matches O(n*l + m*k) [OK]

Hint: Trie build and search costs add up [OK]

Common Mistakes:

• Assuming O(m*n*l) like brute force
• Multiplying k and l unnecessarily

4. What is the time complexity of the optimal Trie + DFS solution for Word Search II, assuming the board has N cells, the maximum word length is L, and there are W words in the list?

medium

A. O(W * N * 4^L) -- checking each word independently with DFS

B. O(N * L) -- linear in board size and max word length due to Trie traversal

C. O(N * 4^L) -- DFS from each cell with pruning by Trie prefixes

D. O(W * L) -- building Trie and searching each word once

Solution

1. Step 1: Identify DFS calls from each cell

   DFS explores up to 4 directions per step, up to length L, so worst-case 4^L paths per cell.

2. Step 2: Consider Trie pruning

   Trie pruning cuts many paths early, but worst-case still O(N * 4^L) in theory.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Brute force per word is O(W * N * 4^L), which is much worse [OK]

Hint: Trie pruning reduces but worst-case DFS is exponential in L [OK]

Common Mistakes:

• Confusing W factor in complexity
• Ignoring exponential DFS branching
• Assuming linear time due to Trie

5. Suppose you want to extend the Trie to support deletion of words. Which of the following approaches correctly handles deletion without breaking prefix searches for other words?

hard

A. Remove the isEnd flag at the last node of the word and delete nodes bottom-up only if they have no children and isEnd is false

B. Delete all nodes corresponding to the word immediately, regardless of children

C. Set isEnd to false at the last node but never delete any nodes

D. Rebuild the entire trie after each deletion to remove unused nodes

Solution

1. Step 1: Understand deletion impact

   Removing isEnd flag marks word as deleted. Nodes can be deleted only if they are not prefixes of other words.

2. Step 2: Delete nodes bottom-up conditionally

   Delete nodes only if they have no children and isEnd is false to avoid breaking other words.

3. Step 3: Avoid unsafe deletions

   Deleting nodes immediately or rebuilding trie is inefficient or breaks other words.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Conditional bottom-up deletion preserves trie correctness [OK]

Hint: Delete nodes only if no children and isEnd is false [OK]

Common Mistakes:

• Deleting nodes without checking children breaks other words