Implement Trie (Prefix Tree) - aloalgo
aloalgo logoaloalgo
Beta
Problems
Login

Implement Trie (Prefix Tree)

Medium

Implement a trie (prefix tree) with insert, search, and startsWith methods. The trie should support the following operations:

  • insert(word: string) => void: Inserts a word into the trie.
  • search(word: string) => boolean: Returns true if the word is in the trie, otherwise false.
  • startsWith(prefix: string) => boolean: Returns true if there is a word in the trie that starts with the given prefix, otherwise false.

YouYou may assume that all input words consist of lowercase English letters.

Example 1

Input
t = Trie()
t.insert("apple")
t.search("apple")
t.search("app")
t.starts_with("app")
t.insert("app")
t.search("app")
Output
[True, False, True, True]
Explanation:

After inserting 'apple', searching for 'apple' returns true, while searching for 'app' returns false. However, 'app' is a prefix of 'apple', so startsWith('app') returns true. After inserting 'app', searching for 'app' now returns true.

Example 2

Input
t = Trie()
t.insert("banana")
t.starts_with("ban")
t.search("ban")
t.insert("band")
t.starts_with("ban")
t.search("band")
Output
[True, False, True, True]
Explanation:

After inserting banana into the trie, startsWith('ban') returns true since 'ban' is a prefix of 'banana'. However, searching for 'ban' returns false as it is not a complete word in the trie. After inserting 'band', startsWith('ban') still returns true, and searching for 'band' returns true as it has been added to the trie.

Loading...
Case 1Case 2
Input
t = Trie()
t.insert("apple")
t.search("apple")
t.search("app")
t.starts_with("app")
t.insert("app")
t.search("app")
Output
[True, False, True, True]
🤖

Hello! I am your ✨ AI assistant. I can provide you hints, explanations, give feedback on your code, and more. Just ask me anything related to the problem you're working on!