source: https://leetcode.com/problems/implement-trie-prefix-tree/
Implement Trie (Prefix Tree)
A trie (pronounced as “try”) or prefix tree is a tree data structure used to efficiently store and retrieve keys in a dataset of strings. There are various applications of this data structure, such as autocomplete and spellchecker.
Implement the Trie class:
- Trie() Initializes the trie object.
- void insert(String word) Inserts the string word into the trie.
- boolean search(String word) Returns true if the string word is in the trie (i.e., was inserted before), and false otherwise.
- boolean startsWith(String prefix) Returns true if there is a previously inserted string word that has the prefix prefix, and false otherwise.
Example 1:
Input
[“Trie”, “insert”, “search”, “search”, “startsWith”, “insert”, “search”]
[[], [“apple”], [“apple”], [“app”], [“app”], [“app”], [“app”]]
Output
[null, null, true, false, true, null, true]
Explanation
Trie trie = new Trie();
trie.insert(“apple”);
trie.search(“apple”); // return True
trie.search(“app”); // return False
trie.startsWith(“app”); // return True
trie.insert(“app”);
trie.search(“app”); // return True
Constraints:
- 1 <= word.length, prefix.length <= 2000
- word and prefix consist only of lowercase English letters.
- At most 3 * 104 calls in total will be made to insert, search, and startsWith.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 |
class Trie { private TrieNode root; public Trie() { this.root = new TrieNode('*'); } public void insert(String word) { TrieNode node = this.root; char[] cArr = word.toCharArray(); for(char c: cArr){ if(!node.kids.containsKey(c)){ node.kids.put(c, new TrieNode(c)); } node = node.kids.get(c); } node.isWord = true; } public boolean search(String word) { TrieNode node = this.root; char[] cArr = word.toCharArray(); for(char c: cArr){ if(node.kids.containsKey(c)){ node = node.kids.get(c); } else { return false; } } return node.isWord; } public boolean startsWith(String prefix) { TrieNode node = this.root; char[] cArr = prefix.toCharArray(); for(char c: cArr){ if(node.kids.containsKey(c)){ node = node.kids.get(c); } else { return false; } } return true; } static class TrieNode { char val; Map<Character, TrieNode> kids; boolean isWord; public TrieNode(char val){ this.kids = new HashMap<>(); } } } /** * Your Trie object will be instantiated and called as such: * Trie obj = new Trie(); * obj.insert(word); * boolean param_2 = obj.search(word); * boolean param_3 = obj.startsWith(prefix); */ |
- Let’s say n is the number of characters in a string
- Let’s k is the total number of strings you want to insert
Time Complexity:
Search: O(n)
Insert: O(n)
startsWith: O(n)
Space Complexity:
O(n*k)