Question
Formatted question description: https://leetcode.ca/all/208.html
208 Implement Trie (Prefix Tree)
Implement a trie with methods
insert
search
startsWith
Note:
You may assume that all inputs are consist of lowercase letters a-z.
@tag-trie
Algorithm
Each node of the alphabetic dictionary tree defines an array of child node pointers with a size of 26
, and then uses a marker to record whether it is a word up to the current position.
When initializing, the 26
child nodes are all empty.
Then the insert()
operation only needs to calculate the position of each character of the string to be inserted, and then find out whether this child node exists, if it does not exist, create a new one, and then move to the next one.
The word search()
and prefix search operations are very similar to the insert operation. The difference is that if there are no child nodes, false is returned. At the end of the search time, you need to look at the flag, and you can directly return true when you search the prefix.
Code
Java
-
public class Implement_Trie_Prefix_Tree { public static void main(String[] args) { Implement_Trie_Prefix_Tree out = new Implement_Trie_Prefix_Tree(); Trie trie = out.new Trie(); trie.insert("abc"); trie.insert("ab"); System.out.println(trie.search("ab")); trie.insert("ab"); System.out.println(trie.search("ab")); System.out.println(trie.startsWith("a")); } class TrieNode { // R children to node children private TrieNode[] children; private final int R = 26; private boolean isEnd; public TrieNode() { children = new TrieNode[R]; } public boolean containsKey(char ch) { return children[ch - 'a'] != null; } public TrieNode get(char ch) { return children[ch - 'a']; } public void put(char ch, TrieNode node) { children[ch - 'a'] = node; } public void setEnd() { isEnd = true; } public boolean isEnd() { return isEnd; } } class Trie { private TrieNode root; public Trie() { root = new TrieNode(); } // Inserts a word into the trie. public void insert(String word) { TrieNode node = root; // @note:@memorize: iteration is better than recursion during trie building for (int i = 0; i < word.length(); i++) { char currentChar = word.charAt(i); if (!node.containsKey(currentChar)) { node.put(currentChar, new TrieNode()); } node = node.get(currentChar); } node.setEnd(); } // search a prefix or whole key in trie and // returns the node where search ends private TrieNode searchPrefix(String word) { TrieNode node = root; for (int i = 0; i < word.length(); i++) { char curLetter = word.charAt(i); if (node.containsKey(curLetter)) { node = node.get(curLetter); } else { return null; } } return node; } // Returns if the word is in the trie. public boolean search(String word) { TrieNode node = searchPrefix(word); return node != null && node.isEnd(); } // Returns if there is any word in the trie // that starts with the given prefix. public boolean startsWith(String prefix) { TrieNode node = searchPrefix(prefix); return node != null; } } // Your Trie object will be instantiated and called as such: // Trie trie = new Trie(); // trie.insert("somestring"); // trie.search("key"); }
-
// OJ: https://leetcode.com/problems/implement-trie-prefix-tree/ // Time: O(W) for insert/search/startsWith // Space: O(1) extra space for all struct TrieNode { TrieNode *next[26] = {}; bool word = false; }; class Trie { TrieNode root; TrieNode *find(string &word) { auto node = &root; for (char c : word) { if (!node->next[c - 'a']) return NULL; node = node->next[c - 'a']; } return node; } public: void insert(string word) { auto node = &root; for (char c : word) { if (!node->next[c - 'a']) node->next[c - 'a'] = new TrieNode(); node = node->next[c - 'a']; } node->word = true; } bool search(string word) { auto node = find(word); return node && node->word; } bool startsWith(string prefix) { return find(prefix); } };
-
import collections class TrieNode: def __init__(self): ''' Usually, a Python dictionary throws a KeyError if you try to get an item with a key that is not currently in the dictionary. The defaultdict in contrast will simply create any items that you try to access https://stackoverflow.com/questions/5900578/how-does-collections-defaultdict-work ''' self.child = collections.defaultdict(TrieNode) self.is_word = False class Trie: def __init__(self): self.root = TrieNode() def insert(self, word: str) -> None: cur = self.root for letter in word: cur = cur.child[letter] cur.is_word = True def search(self, word: str) -> bool: cur = self.root for letter in word: # cur = cur.child[letter] ==> will not work, it will creat a default node for this letter cur = cur.child.get(letter) if not cur: return False return cur.is_word def startsWith(self, prefix: str) -> bool: cur = self.root for letter in prefix: # cur = cur.child[letter] ==> will not work, it will creat a default node for this letter cur = cur.child.get(letter) if not cur: return False return True # Your Trie object will be instantiated and called as such: # obj = Trie() # obj.insert(word) # param_2 = obj.search(word) # param_3 = obj.startsWith(prefix) # below is using reduce() class Trie(object): def __init__(self): T = lambda: collections.defaultdict(T) self.root = T() def insert(self, word): reduce(dict.__getitem__, word, self.root)['#'] = True def search(self, word): return '#' in reduce(lambda cur, c: cur.get(c, {}), word, self.root) def startsWith(self, prefix): return bool(reduce(lambda cur, c: cur.get(c, {}), prefix, self.root))