Prefix Search and Starts-With
Add a starts_with method that returns true if any inserted word shares a given prefix, and use it to implement autocomplete suggestions.
The Power of Prefix Queries
The trie's defining advantage over a hash map is efficient prefix querying. A prefix query answers: 'how many stored words start with this prefix?', 'what are all stored words with this prefix?', or simply 'does any word with this prefix exist?'. These queries are O(p) where p is the prefix length, independent of the total number of words stored — making tries ideal for autocomplete and search suggestions.
The starts_with Method
starts_with(prefix) returns True if any stored word begins with the given prefix. Traverse the trie following each character of the prefix. If all characters can be followed without a missing edge, the prefix exists and at least one word starts with it. The implementation is identical to search except we return True as soon as we finish traversing — we don't check is_end.
class TrieNode:
def __init__(self):
self.children = {}
self.is_end = False
class Trie:
def __init__(self):
self.root = TrieNode()
def insert(self, word):
node = self.root
for c in word:
if c not in node.children:
node.children[c] = TrieNode()
node = node.children[c]
node.is_end = True
def starts_with(self, prefix):
node = self.root
for c in prefix:
if c not in node.children:
return False
node = node.children[c]
return True
t = Trie()
for w in ['hello','help','world','word']:
t.insert(w)
print(t.starts_with('hel')) # True
print(t.starts_with('wor')) # True
print(t.starts_with('xyz')) # FalseAll lessons in this course
- TrieNode Class: Insert and Search
- Prefix Search and Starts-With
- Wildcard and Regex Search in a Trie
- Word Search II: Trie + Backtracking on Grid