Longest Word in Dictionary

▶

Steps

setup

Initialize Trie and Root Node

Create an empty trie with a root node that has no children and does not mark the end of any word.

💡 The root node is the starting point for all insertions and searches; it represents an empty prefix.

Line:

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

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

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

insert

Insert word 'w' into Trie

Start inserting the first word 'w'. Since 'w' is not in root's children, create a new node for 'w' and mark it as end of word.

💡 Inserting the first word creates the first branch in the trie.

Line:

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

💡 A new node is created for 'w' and marked as a complete word node.

insert

Insert word 'wo' into Trie

Insert 'wo'. The 'w' node exists, so move to it. 'o' does not exist under 'w', create a new node for 'o' and mark it as end of word.

💡 Words sharing prefixes reuse existing nodes, saving space and time.

Line:

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

💡 The trie branches from 'w' to 'o', marking 'wo' as a complete word.

insert

Insert word 'wor' into Trie

Insert 'wor'. Nodes for 'w' and 'o' exist, move through them. 'r' does not exist under 'o', create node for 'r' and mark end of word.

💡 Insertion continues down existing prefix nodes before adding new nodes.

Line:

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

💡 The trie extends from 'wo' to 'wor', marking 'wor' as a complete word.

insert

Insert word 'worl' into Trie

Insert 'worl'. Traverse existing nodes for 'w', 'o', 'r'. 'l' does not exist under 'r', create node for 'l' and mark end of word.

💡 Each longer word extends the trie by one new node after existing prefix nodes.

Line:

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

💡 The trie now includes 'worl' as a complete word extending from 'wor'.

insert

Insert word 'world' into Trie

Insert 'world'. Traverse existing nodes for 'w', 'o', 'r', 'l'. 'd' does not exist under 'l', create node for 'd' and mark end of word.

💡 The longest word extends the trie by one final node.

Line:

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

💡 The trie now contains all words, with 'world' as the longest word node.

setup

Initialize BFS Queue with Root Node

Start BFS traversal by initializing a queue containing only the root node. The longest word found so far is empty.

💡 BFS will explore nodes level by level to find the longest valid word.

Line:

queue = deque([trie.root])
longest = ""

💡 The BFS queue starts with the root to explore all valid word paths.

traverse

BFS: Dequeue Root and Enqueue Child 'w'

Dequeue the root node. Check its children. 'w' node marks a complete word, so enqueue it for BFS and update longest word to 'w'.

💡 Only nodes marking complete words are enqueued to ensure all prefixes exist.

Line:

node = queue.popleft()
for ch in sorted(node.children.keys()):
    child = node.children[ch]
    if child.word is not None:
        queue.append(child)
        if len(child.word) > len(longest) or (len(child.word) == len(longest) and child.word < longest):
            longest = child.word

💡 BFS explores only valid word nodes, ensuring prefix validity.

traverse

BFS: Dequeue 'w' and Enqueue Child 'o'

Dequeue node 'w'. Check children. 'o' node marks a complete word, enqueue it and update longest word to 'wo' since it is longer.

💡 BFS continues level by level, updating longest word when a longer valid word is found.

Line:

node = queue.popleft()
for ch in sorted(node.children.keys()):
    child = node.children[ch]
    if child.word is not None:
        queue.append(child)
        if len(child.word) > len(longest) or (len(child.word) == len(longest) and child.word < longest):
            longest = child.word

💡 The longest word is updated as BFS finds longer valid words.

traverse

BFS: Dequeue 'o' and Enqueue Child 'r'

Dequeue node 'o'. Check children. 'r' node marks a complete word, enqueue it and update longest word to 'wor'.

💡 BFS ensures only nodes marking complete words are enqueued, maintaining prefix validity.

Line:

node = queue.popleft()
for ch in sorted(node.children.keys()):
    child = node.children[ch]
    if child.word is not None:
        queue.append(child)
        if len(child.word) > len(longest) or (len(child.word) == len(longest) and child.word < longest):
            longest = child.word

💡 The longest word is updated as BFS finds longer valid words.

traverse

BFS: Dequeue 'r' and Enqueue Child 'l'

Dequeue node 'r'. Check children. 'l' node marks a complete word, enqueue it and update longest word to 'worl'.

💡 BFS continues to explore valid word nodes deeper in the trie.

Line:

node = queue.popleft()
for ch in sorted(node.children.keys()):
    child = node.children[ch]
    if child.word is not None:
        queue.append(child)
        if len(child.word) > len(longest) or (len(child.word) == len(longest) and child.word < longest):
            longest = child.word

💡 The longest word is updated to the next longer valid prefix.

traverse

BFS: Dequeue 'l' and Enqueue Child 'd'

Dequeue node 'l'. Check children. 'd' node marks a complete word, enqueue it and update longest word to 'world'.

💡 BFS finds the longest word by exploring all valid prefixes.

Line:

node = queue.popleft()
for ch in sorted(node.children.keys()):
    child = node.children[ch]
    if child.word is not None:
        queue.append(child)
        if len(child.word) > len(longest) or (len(child.word) == len(longest) and child.word < longest):
            longest = child.word

💡 The longest word is updated to the full word 'world'.

search

BFS: Queue Empty, Return Longest Word

The queue is now empty, BFS traversal is complete. The longest word found is 'world'.

💡 The BFS traversal ensures the longest word with all prefixes present is found.

Line:

return longest

💡 The algorithm returns the longest valid word after exploring all valid prefixes.

from collections import deque

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

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

    def insert(self, word):
        node = self.root
        for ch in word:  # STEP 2-6: Insert each character
            if ch not in node.children:
                node.children[ch] = TrieNode()  # STEP: Create new node
            node = node.children[ch]
        node.word = word  # STEP: Mark end of word

def longestWord(words):
    trie = Trie()  # STEP 1: Initialize trie
    for word in words:
        trie.insert(word)  # STEP 2-6: Insert all words
    queue = deque([trie.root])  # STEP 7: Initialize BFS queue
    longest = ""
    while queue:
        node = queue.popleft()  # STEP 8-12: Dequeue node
        for ch in sorted(node.children.keys()):
            child = node.children[ch]
            if child.word is not None:  # STEP: Only enqueue nodes marking complete words
                queue.append(child)
                if len(child.word) > len(longest) or (len(child.word) == len(longest) and child.word < longest):
                    longest = child.word  # STEP: Update longest word
    return longest  # STEP 13: Return result

if __name__ == "__main__":
    words = ["w","wo","wor","worl","world"]
    print(longestWord(words))  # Output: world

📊

Longest Word in Dictionary - Watch the Algorithm Execute, Step by Step

Watching the trie construction and BFS traversal visually reveals how the algorithm ensures all prefixes exist before considering a word, which is hard to grasp from code alone.

insert

insert

w

w*

insert

wo

w*o*

insert

wor

w*o*r*

insert

worl

w*o*r*l*

insert

world

w*o*r*l*d*

search

w*o*r*l*d*

search

w

w*o*r*l*d*

search

wo

w*o*r*l*d*

search

wor

w*o*r*l*d*

search

worl

w*o*r*l*d*

search

world

w*o*r*l*d*

search

world

w*o*r*l*d*

Search: true

Key Takeaways

✓ The trie structure efficiently shares prefixes among words, reducing redundant storage.

This is hard to see from code alone because the sharing happens implicitly in the data structure.

✓ BFS traversal only enqueues nodes that mark complete words, ensuring all prefixes exist for candidate words.

This filtering step is crucial and not obvious without visualizing the traversal.

✓ The longest word is updated dynamically during BFS, reflecting the lexicographically smallest word when lengths tie.

Understanding this tie-breaking rule is easier when watching the word updates step-by-step.

Practice

1. Given a string text and a list of words, you need to find all pairs of indices [i, j] such that the substring text[i:j+1] is in the list of words. Which approach guarantees an optimal solution in terms of time complexity when the list of words is large and words have varying lengths?

easy

A. Build a trie from the list of words and perform a DFS from each index in the text to find matching substrings.

B. Use dynamic programming to store whether substrings are in the word list and build results bottom-up.

C. Use a brute force nested loop to check every substring against the list of words directly.

D. Sort the list of words and use binary search to check each substring generated from the text.

Solution

1. Step 1: Understand the problem constraints

   The problem requires finding all substrings of text that match any word in a large list. Checking every substring against the list directly is expensive.

2. Step 2: Recognize the trie + DFS pattern

   Building a trie from the words allows prefix-based pruning. DFS from each index in text efficiently finds all matching substrings without redundant checks, guaranteeing optimal time.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Trie + DFS prunes search space better than brute force or binary search [OK]

Hint: Trie + DFS prunes prefix search efficiently [OK]

Common Mistakes:

• Thinking brute force is efficient enough for large inputs

2. Consider the following Python code implementing the trie + DFS approach to find index pairs of substrings matching words. Given text = "abcab" and words = ["ab", "bc", "ca"], what is the final sorted list res returned by indexPairs(text, words)?

easy

A. [[0,1],[1,2],[3,4]]

B. [[0,1],[1,2],[2,3]]

C. [[0,1],[2,3],[3,4]]

D. [[0,1],[1,2],[2,3],[3,4]]

Solution

1. Step 1: Build the trie from words ["ab", "bc", "ca"]

   The trie has branches for 'a'->'b', 'b'->'c', and 'c'->'a', each marking word_end at the last character.

2. Step 2: DFS from each index in text "abcab"

   From index 0: 'a'->'b' matches "ab" -> [0,1]. From index 1: 'b'->'c' matches "bc" -> [1,2]. From index 2: 'c'->'a' matches "ca" -> [2,3]. From index 3: 'a'->'b' matches "ab" -> [3,4]. From index 4: 'b' no further match.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   All four pairs found and sorted correctly [OK]

Hint: Trace DFS from each index carefully [OK]

Common Mistakes:

• Missing last match at index 3
• Off-by-one in end index

3. Consider the following buggy insert method for MapSum. Which line contains the subtle bug that causes incorrect sum queries after updating an existing key's value?

medium

A. Line where root node sum update is commented out

B. Line where delta is computed

C. Line where map[key] is updated

D. Line where child node sum is updated

Solution

1. Step 1: Understand delta and map update

   Delta correctly computes difference; map updated correctly.

2. Step 2: Identify missing root sum update

   Root node sum update is commented out, so total sums are stale, causing incorrect sum queries.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Root sum must be updated to keep prefix sums accurate [OK]

Hint: Root sum update is critical for correct prefix sums [OK]

Common Mistakes:

• Forgetting root sum update
• Updating map incorrectly
• Misplacing child sum updates

4. Examine the following buggy code snippet for building the trie and collecting suggestions. Which line contains the subtle bug that can cause incorrect suggestion ordering or runtime errors?

medium

A. Line with 'products.sort()' missing before building trie

B. Line with 'for product in products:' loop

C. Line with 'if len(node.suggestions) < 3:' condition

D. Line with 'if node and ch in node.children:' during search

Solution

1. Step 1: Identify missing sorting

   The code does not sort products before building the trie, so suggestions are appended in input order, not lex order.

2. Step 2: Consequences of missing sort

   Without sorting, the suggestions list at each node is not guaranteed to be lexicographically smallest three, violating problem requirements.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Sorting before trie build is essential for correct lex order [OK]

Hint: Always sort products before building trie for lex order [OK]

Common Mistakes:

• Forgetting to sort products
• Appending suggestions without limit
• Not handling missing prefix nodes

5. Suppose the problem is modified so that pairs can be counted multiple times if elements are reused (i.e., pairs (i, j) with i and j possibly equal). Which modification to the bitwise trie approach correctly handles this scenario?

hard

A. Modify the query function to include the current number in the trie before querying to count pairs with itself.

B. No change needed; the existing approach already counts pairs with reuse.

C. Insert all numbers into the trie first, then for each number query the trie for counts less than limit, allowing reuse.

D. Use a frequency map instead of a trie since reuse breaks trie assumptions.

Solution

1. Step 1: Understand reuse means pairs can include the same element twice

   Counting pairs with i == j means the current number must be considered in queries.

2. Step 2: Modify insertion and query order

   Insert the current number into the trie before querying so it can pair with itself and others, enabling reuse counting.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Inserting before querying allows counting pairs including the current element [OK]

Hint: Insert before query to count pairs with reuse [OK]

Common Mistakes:

• Assuming no change needed
• Inserting after query (misses self pairs)
• Switching to frequency map unnecessarily