Trie
Prefix Matching
DESCRIPTION
Use a Trie to implement a prefix matching function.
- match(prefix) returns a list of all words in the Trie that start with the given prefix. The words can be in any order.
The creation of the Trie is already implemented for you.
The test cases include two parameters:
- words: a list of words to add to the Trie,
- prefix: a prefix to search for.
The test cases will create the Trie with the initial words, and then run the match command, and compare the output to the expected output.
Example 1:
Input:
initialWords = ["apple", "app", "apartment", "ap", "apricot"] prefix = "app"
Output: ["apple", "app"]
Example 2:
Input:
initialWords = ["ball", "bath", "bat", "batter"] prefix = "bat"
Output: ["bat", "bath", "batter"]
Explanation
Step 1: Search for the Prefix
def prefix(self, word):"""Return a list of all words in the triethat start with the given prefix."""node = self.rootfor char in word:if char not in node.children:return [] # Prefix not found in trienode = node.children[char]
Step 2: Perform Depth-First Search
def prefix(self, word):"""Return a list of all words in the trie that start with the given prefix."""node = self.rootfor char in word:if char not in node.children:return [] # Prefix not found in trienode = node.children[char]# Now perform DFS to collect all wordsresult = []def dfs(current_node, current_word):if current_node.isEndOfWord:result.append(current_word)for char, child_node in current_node.children.items():dfs(child_node, current_word + char)dfs(node, word)return result
Test Your Knowledge
Login to take the complexity quiz and track your progress
Complexity Analysis
Time Complexity: O(N + M) where N is the length of the prefix and M is the number of characters in the words that have the given prefix. We search for the prefix in the trie in O(N) time and perform a depth-first search to find all words in O(M) time.
Space Complexity: O(M) where M is the number of characters in matching words. The space complexity is dominated by the output list that stores all words matching the given prefix, while the call stack space is only proportional to the length of the longest matching word.
Your account is free and you can post anonymously if you choose.