Backend Engineering
Senior
programming
LeetCode #208 - Implement Trie (Prefix Tree)
Given a list of words, implement a trie with insert, search, and startsWith methods. Your implementation should support insert and search queries efficiently.
Input: ['apple', 'app'], search('app') -> true
Input: ['apple', 'app'], startsWith('ap') -> true
Method Signatures:
def insert(self, word: str) -> None:
pass
def search(self, word: str) -> bool:
pass
def startsWith(self, prefix: str) -> bool:
pass Input/Output:
Input: ['apple', 'app'], search('app') -> true
Input: ['apple', 'app'], startsWith('ap') -> true
Constraints:
- All input words are lowercase alphabets.
- Insert, search, and startsWith operations should be efficient (preferably O(M) where M is the length of the word).
Suggested Answer