Shortest Unique Prefix for Every Word

▶

Steps

setup

Initialize Trie Root

Create the root node of the trie with no children and frequency zero. This node is the starting point for all insertions.

💡 The root node is essential as the anchor point for all words inserted into the trie.

Line:

class TrieNode:
    def __init__(self):
        self.children = {}
        self.freq = 0

💡 The trie starts empty with a single root node.

insert

Insert 'zebra' - Add 'z' Node

Insert the first character 'z' of 'zebra'. Since 'z' is not a child of root, create a new node for 'z' and increment its frequency to 1.

💡 Creating new nodes for characters not yet in the trie builds the structure for the word.

Line:

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

💡 New branches are created for unique characters at their position in the word.

insert

Insert 'zebra' - Add 'e' Node

Insert character 'e' after 'z'. Since 'e' is not a child of 'z', create a new node for 'e' and set frequency to 1.

💡 Each new character extends the path for the word in the trie.

Line:

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

💡 The trie path for 'zebra' grows with each new character.

insert

Insert 'zebra' - Add 'b', 'r', 'a' Nodes

Continue inserting 'b', 'r', and 'a' nodes sequentially, each new character creating a new node with frequency 1.

💡 Completing the insertion of a word involves adding nodes for all its characters.

Line:

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

💡 The full path for 'zebra' is now represented in the trie with frequency 1 at each node.

insert

Insert 'dog' - Add 'd' Node

Insert 'dog'. Since 'd' is not a child of root, create a new node for 'd' with frequency 1.

💡 New words starting with different letters create new branches from root.

Line:

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

💡 The trie now has two branches from root: 'z' and 'd'.

insert

Insert 'dog' - Add 'o' and 'g' Nodes

Insert 'o' and 'g' nodes sequentially under 'd', each new node created with frequency 1. Mark 'g' as end of word.

💡 Completing insertion of 'dog' by adding remaining characters.

Line:

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

💡 The word 'dog' is now fully represented in the trie.

insert

Insert 'duck' - Share 'd' Node, Add 'u', 'c', 'k'

Start inserting 'duck'. The 'd' node exists, so increment its frequency to 2. Create new nodes for 'u', 'c', and 'k' with frequency 1 each.

💡 Shared prefixes reuse existing nodes, increasing frequency counts.

Line:

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

💡 Frequency counts reflect how many words share a prefix node.

insert

Insert 'dove' - Share 'd' and 'o' Nodes, Add 'v' and 'e'

Insert 'dove'. 'd' and 'o' nodes exist, increment their frequencies to 3 and 2 respectively. Create new nodes for 'v' and 'e' with frequency 1 each.

💡 Shared prefixes increase frequency counts, new branches created for diverging characters.

Line:

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

💡 Frequency counts help identify how many words share each prefix node.

traverse

Find Unique Prefix for 'zebra' - Traverse to 'z' Node

Start searching for the shortest unique prefix of 'zebra'. Move from root to 'z'. The frequency at 'z' is 1, so prefix 'z' is unique.

💡 A frequency of 1 means no other word shares this prefix, so we can stop here.

Line:

for ch in word:
    prefix += ch
    node = node.children[ch]
    if node.freq == 1:
        return prefix

💡 The shortest unique prefix for 'zebra' is 'z'.

traverse

Find Unique Prefix for 'dog' - Traverse 'd' -> 'o' -> 'g'

Traverse nodes for 'dog'. Frequencies at 'd' and 'o' are greater than 1, so continue. At 'g', frequency is 1, so prefix 'dog' is unique.

💡 We must traverse until frequency 1 to find the unique prefix.

Line:

for ch in word:
    prefix += ch
    node = node.children[ch]
    if node.freq == 1:
        return prefix

💡 The entire word 'dog' is needed as prefix to be unique.

traverse

Find Unique Prefix for 'duck' - Traverse 'd' -> 'u'

Traverse 'd' and 'u' nodes. Frequency at 'd' is 3, at 'u' is 1, so prefix 'du' is unique for 'duck'.

💡 Finding the first node with frequency 1 gives the shortest unique prefix.

Line:

for ch in word:
    prefix += ch
    node = node.children[ch]
    if node.freq == 1:
        return prefix

💡 Prefix 'du' uniquely identifies 'duck'.

traverse

Find Unique Prefix for 'dove' - Traverse 'd' -> 'o' -> 'v'

Traverse nodes 'd', 'o', and 'v'. Frequencies at 'd' and 'o' are >1, at 'v' is 1, so prefix 'dov' is unique.

💡 The unique prefix may require multiple characters if shared prefixes exist.

Line:

for ch in word:
    prefix += ch
    node = node.children[ch]
    if node.freq == 1:
        return prefix

💡 Prefix 'dov' uniquely identifies 'dove'.

reconstruct

Final Output: Shortest Unique Prefixes

Collect the shortest unique prefixes found for each word: 'z', 'dog', 'du', and 'dov'.

💡 The final prefixes uniquely identify each word in the list.

Line:

return [trie.unique_prefix(w) for w in words]

💡 The trie frequency counts enable efficient retrieval of shortest unique prefixes.

class TrieNode:
    def __init__(self):
        self.children = {}  # STEP 1
        self.freq = 0      # STEP 1

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

    def insert(self, word):
        node = self.root  # STEP 2
        for ch in word:   # STEP 2-8 loop
            if ch not in node.children:  # STEP 2-8 decision
                node.children[ch] = TrieNode()  # STEP 2-8 insert
            node = node.children[ch]  # STEP 2-8 move
            node.freq += 1  # STEP 2-8 freq update

    def unique_prefix(self, word):
        node = self.root  # STEP 9
        prefix = ''      # STEP 9
        for ch in word:  # STEP 9-12 loop
            prefix += ch  # STEP 9-12 build prefix
            node = node.children[ch]  # STEP 9-12 move
            if node.freq == 1:  # STEP 9-12 check
                return prefix  # STEP 9-12 return
        return prefix  # fallback

def shortest_unique_prefix(words):
    trie = Trie()  # STEP 1
    for w in words:  # STEP 2-8
        trie.insert(w)  # STEP 2-8
    return [trie.unique_prefix(w) for w in words]  # STEP 9-13

if __name__ == '__main__':
    words = ["zebra", "dog", "duck", "dove"]  # input
    print(shortest_unique_prefix(words))  # output

📊

Shortest Unique Prefix for Every Word - Watch the Algorithm Execute, Step by Step

Watching the trie construction and prefix search step-by-step reveals how frequency counts help identify unique prefixes efficiently, which is hard to grasp by reading code alone.

insert

insert

zebra

z

insert

zebra

ze

insert

zebra

zebra*

insert

dog

zebra*d

insert

dog

zebra*dog*

insert

duck

zebra*dog*uck*

insert

dove

zebra*dog*uck*ve*

search

zebra

zebra*dog*uck*ve*

Search: true

search

dog

zebra*dog*uck*ve*

Search: true

search

duck

zebra*dog*uck*ve*

Search: true

search

dove

zebra*dog*uck*ve*

Search: true

reconstruct

zebra*dog*uck*ve*

Key Takeaways

✓ Frequency counts at each trie node enable efficient identification of shortest unique prefixes.

This insight is difficult to see from code alone because frequency updates and their role in prefix uniqueness are implicit.

✓ Shared prefixes increase node frequencies, requiring traversal deeper into the trie to find unique prefixes.

Visualizing frequency counts clarifies why some words need longer prefixes to be unique.

✓ The trie structure grows dynamically, reusing nodes for shared prefixes and creating new nodes only when necessary.

Seeing node creation and reuse step-by-step helps understand trie efficiency and memory usage.

Practice

1. Consider the following Python code implementing the optimal StreamChecker. Given the words ["cd", "f", "kl"], what is the return value of the query sequence: query('a'), query('b'), query('c'), query('d')? Specifically, what does query('d') return?

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

class StreamChecker:
    def __init__(self, words):
        self.root = TrieNode()
        self.max_len = max(len(w) for w in words)
        self.stream = []
        for word in words:
            node = self.root
            for ch in reversed(word):
                if ch not in node.children:
                    node.children[ch] = TrieNode()
                node = node.children[ch]
            node.is_word = True

    def query(self, letter):
        self.stream.append(letter)
        if len(self.stream) > self.max_len:
            self.stream.pop(0)
        node = self.root
        for ch in reversed(self.stream):
            if ch not in node.children:
                return False
            node = node.children[ch]
            if node.is_word:
                return True
        return False

sc = StreamChecker(["cd", "f", "kl"])
print(sc.query('a'))
print(sc.query('b'))
print(sc.query('c'))
print(sc.query('d'))

easy

A. False

B. True

C. Raises an exception

D. None

Solution

1. Step 1: Trace the stream buffer after queries

   After queries 'a', 'b', 'c', 'd', the stream buffer contains ['a','b','c','d'], but max_len=2, so oldest letters are popped. After 'c', stream=['b','c'], after 'd', stream=['c','d'].

2. Step 2: Traverse trie with reversed stream

   For query('d'), reversed stream is ['d','c']. Trie has reversed words: 'dc' for 'cd'. Traversing 'd' then 'c' hits is_word=True at 'c' node, so returns True. However, the query sequence is query('a'), query('b'), query('c'), query('d'). The query('c') returns False because 'c' alone is not a word. The query('d') returns True because 'cd' is in the dictionary and the stream buffer contains ['c','d'].

3. Step 3: Check query('d') return value

   Since the query('d') returns True, the correct answer is True.

4. Final Answer:

   Option B -> Option B

5. Quick Check:

   Stream buffer limited to max word length matches 'cd' suffix [OK]

Hint: Stream buffer limited to max word length [OK]

Common Mistakes:

• Not limiting stream buffer size
• Not reversing words in trie
• Returning false too early

2. You are given a 2D grid of letters and a list of words. You need to find all words from the list that can be formed by sequentially adjacent letters on the board, where adjacent letters are horizontally or vertically neighboring. Each letter cell may only be used once per word. Which algorithmic approach is best suited to efficiently solve this problem when the word list is large?

easy

A. Build a Trie from the word list and perform a single DFS on the board with prefix pruning using the Trie.

B. Use a brute force DFS for each word independently, checking all paths on the board.

C. Use dynamic programming to store subproblems of partial word matches on the board.

D. Sort the words and use binary search combined with DFS to find matches on the board.

Solution

1. Step 1: Understand problem constraints and prefix sharing

   Multiple words need to be found on the board, and many words may share prefixes, making prefix pruning beneficial.

2. Step 2: Use Trie for efficient prefix pruning during DFS

   Building a Trie allows pruning DFS paths early if no word starts with the current prefix, avoiding redundant searches and improving efficiency.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Trie + DFS reduces search space drastically compared to checking each word separately [OK]

Hint: Trie + DFS prunes invalid prefixes early [OK]

Common Mistakes:

• Thinking brute force DFS per word is efficient
• Assuming DP applies here
• Using sorting and binary search without prefix pruning

3. 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

4. What is the time complexity of the optimal Word Break solution that uses iterative DP combined with a reversed trie for prefix checks, where n is the length of the string and m is the maximum length of words in the dictionary?

medium

A. O(n * log m) due to binary search in trie children

B. O(n^2) because of nested loops over the string

C. O(n * m) because for each position, trie traversal is bounded by max word length

D. O(n * m^2) because each trie traversal can take up to m steps and each step checks children

Solution

1. Step 1: Identify loops and trie traversal cost

   Outer loop runs n times. Inner loop traverses backwards up to m characters (max word length). Trie traversal per character is O(1) on average due to hashmap children.

2. Step 2: Combine to get total complexity

   Total time is O(n * m). Nested loops do not run n^2 because inner loop breaks early when no trie child exists.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Trie traversal bounded by max word length m [OK]

Hint: Trie traversal limits inner loop to max word length [OK]

Common Mistakes:

• Assuming inner loop always runs n times
• Confusing trie traversal cost with binary search
• Ignoring early breaks in inner loop

5. Suppose the problem is modified so that words can be reused multiple times in pairs (i.e., pairs like (i, i) are allowed). Which modification to the Trie + DFS approach correctly handles this variant without producing duplicates or missing pairs?

hard

A. Modify add_word to store all occurrences of the same word and allow same index pairs

B. Keep the check that skips pairs with equal indices but add a separate pass to handle reuse pairs

C. Allow same index pairs by removing index checks but filter duplicates after collecting all pairs

D. Remove the check that skips pairs where indices are equal in search and palindrome_suffixes loops

Solution

1. Step 1: Understand reuse allowance

   Allowing pairs (i, i) means removing index inequality checks but risks duplicates.

2. Step 2: Modify search and add_word accordingly

   Removing index checks alone causes duplicates; filtering duplicates after collection ensures correctness.

3. Step 3: Why other options fail

   Removing checks without filtering causes duplicates; separate pass is inefficient; storing all occurrences is unnecessary.

4. Final Answer:

   Option C -> Option C

5. Quick Check:

   Removing index checks + duplicate filtering handles reuse correctly [OK]

Hint: Allow reuse by removing index checks + filtering duplicates [OK]

Common Mistakes:

• Removing index checks without filtering
• Adding complex separate passes
• Confusing occurrences with indices