Leetcode - Implement Trie (Prefix Tree)
https://leetcode.com/problems/implement-trie-prefix-tree/
Implement a trie with insert, search, and startsWith methods.
Example:
Trie trie = new Trie();
trie.insert("apple");
trie.search("apple"); // returns true
trie.search("app"); // returns false
trie.startsWith("app"); // returns true
trie.insert("app");
trie.search("app"); // returns true
Note:
-
You may assume that all inputs are consist of lowercase letters
a-z. - All inputs are guaranteed to be non-empty strings.
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 62 63 64 65 66 67 68 69 70 71 72 73 74 | type Trie struct { Head *Trie Children []*Trie Leaf bool}/** Initialize your data structure here. */func Constructor() Trie { return Trie{ Head: &Trie{ Children: make([]*Trie, 26), }, }}/** Inserts a word into the trie. */func (this *Trie) Insert(word string) { node := this.Head for i := 0; i < len(word); i++ { index := word[i] - 'a' if node.Children[index] == nil { node.Children[index] = &Trie{ Children: make([]*Trie, 26), } } node = node.Children[index] } node.Leaf = true}/** Returns if the word is in the trie. */func (this *Trie) Search(word string) bool { node := this.Head for i := 0; i < len(word); i++ { index := word[i] - 'a' if node.Children[index] == nil { return false } node = node.Children[index] } if !node.Leaf { return false } return true}/** Returns if there is any word in the trie that starts with the given prefix. */func (this *Trie) StartsWith(prefix string) bool { node := this.Head for i := 0; i < len(prefix); i++ { index := prefix[i] - 'a' if node.Children[index] == nil { return false } node = node.Children[index] } return true}/** * Your Trie object will be instantiated and called as such: * obj := Constructor(); * obj.Insert(word); * param_2 := obj.Search(word); * param_3 := obj.StartsWith(prefix); */ |
评论 (0)
