Sharing the prefix

A tree where the path spells the word. Two fields per node and that is the whole structure.

Key idea

Two fields per node

Each node holds a map from the next character to the child node, and a flag saying whether a word ends here.

That flag is essential and easy to forget. Without it there is no way to tell a complete word from a prefix of a longer one, so a trie holding cart would claim to hold car.

1class Node:2    def __init__(self):3        self.children = {}4        self.ends_here = False5 6# The trie holding "car" and "cart", wired up by hand so the shape is visible.7root = Node()8c = root.children["c"] = Node()9a = c.children["a"] = Node()10r = a.children["r"] = Node()11r.ends_here = True                     # "car" stops here12t = r.children["t"] = Node()13t.ends_here = True                     # and so does "cart"14 15print(sorted(root.children), sorted(r.children))16print(a.ends_here, r.ends_here)

Four nodes for two words. The r node is both an ending and a junction.

Why it works

Searching is one walk, and the two questions differ by one line

To find either a word or a prefix, walk from the root following one character at a time. Failing to find a child means neither exists.

Reaching the end of the input successfully means the prefix exists. Whether a word exists is then a single extra check of the flag on the node you landed on.

Following the same trie by hand makes the difference between the two answers concrete. Both walks below succeed; only one of them lands on a flag.

1class Node:2    def __init__(self):3        self.children = {}4        self.ends_here = False5 6root = Node()                          # the same trie as above: car, cart7c = root.children["c"] = Node()8a = c.children["a"] = Node()9r = a.children["r"] = Node()10r.ends_here = True11r.children["t"] = Node()12r.children["t"].ends_here = True13 14node = root15for ch in "ca":16    node = node.children[ch]17print("walked to the end of 'ca':", node.ends_here)18 19node = root20for ch in "car":21    node = node.children[ch]22print("walked to the end of 'car':", node.ends_here)23 24print("'b' available after 'ca':", "b" in a.children)

Predict the output· 5 min

Predict the output: the missing flag

This trie has no end-of-word flag and treats any successful walk as a word. Type the three values it prints.

Python

1class Node:2    def __init__(self):3        self.children = {}4 5root = Node()6for word in ["cart"]:7    node = root8    for ch in word:9        node = node.children.setdefault(ch, Node())10 11def contains(text):12    node = root13    for ch in text:14        if ch not in node.children:15            return False16        node = node.children[ch]17    return True18 19print(contains("cart"), contains("car"), contains("cab"))

Printed output

Code lab· 25 min

Reading a trie that already exists

A trie is given as nested dictionaries, where a # key marks the end of a stored word. count_words reports how many words the whole trie holds. count_with_prefix reports how many of them begin with a given prefix. longest_stored_prefix_of returns the longest stored word that is a prefix of the given text, or the empty string if there is none.

solution.py

Tests

print(count_words(TRIE), count_words({}))print(count_with_prefix(TRIE, "ca"), count_with_prefix(TRIE, "do"), count_with_prefix(TRIE, "z"), count_with_prefix(TRIE, ""))print(longest_stored_prefix_of(TRIE, "cartoon"), longest_stored_prefix_of(TRIE, "carbon"), repr(longest_stored_prefix_of(TRIE, "zebra")))

Output

Run tests to see output.

Problem· 22 min

Implement Trie Prefix Tree

Read the constraints first and let them tell you what complexity is expected. Derive the approach, implement it, run the tests, and submit when it passes.

1class Node:2 def __init__(self):3 self.children = {}4 self.ends_here = False5 6# The trie holding "car" and "cart", wired up by hand so the shape is visible.7root = Node()8c = root.children["c"] = Node()9a = c.children["a"] = Node()10r = a.children["r"] = Node()11r.ends_here = True # "car" stops here12t = r.children["t"] = Node()13t.ends_here = True # and so does "cart"14 15print(sorted(root.children), sorted(r.children))16print(a.ends_here, r.ends_here)

1class Node:2 def __init__(self):3 self.children = {}4 self.ends_here = False5 6root = Node() # the same trie as above: car, cart7c = root.children["c"] = Node()8a = c.children["a"] = Node()9r = a.children["r"] = Node()10r.ends_here = True11r.children["t"] = Node()12r.children["t"].ends_here = True13 14node = root15for ch in "ca":16 node = node.children[ch]17print("walked to the end of 'ca':", node.ends_here)18 19node = root20for ch in "car":21 node = node.children[ch]22print("walked to the end of 'car':", node.ends_here)23 24print("'b' available after 'ca':", "b" in a.children)

1class Node:2 def __init__(self):3 self.children = {}4 5root = Node()6for word in ["cart"]:7 node = root8 for ch in word:9 node = node.children.setdefault(ch, Node())10 11def contains(text):12 node = root13 for ch in text:14 if ch not in node.children:15 return False16 node = node.children[ch]17 return True18 19print(contains("cart"), contains("car"), contains("cab"))

print(count_words(TRIE), count_words({}))print(count_with_prefix(TRIE, "ca"), count_with_prefix(TRIE, "do"), count_with_prefix(TRIE, "z"), count_with_prefix(TRIE, ""))print(longest_stored_prefix_of(TRIE, "cartoon"), longest_stored_prefix_of(TRIE, "carbon"), repr(longest_stored_prefix_of(TRIE, "zebra")))