208. Implement Trie (Prefix Tree)
Implement a trie with insert, search, and startsWith methods.
Example:
代码语言：javascript复制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 trueNote:
- You may assume that all inputs are consist of lowercase letters
a-z. - All inputs are guaranteed to be non-empty strings.
思路：
题目意思很明确，就是实现一下前缀树的几个api，前缀树有用在路由匹配等场景，具体思路都差不多，实现出来之后，可以有很多优化的点，比如插入前缀一个单词等。这里写一下最基本的一个写法，这里使用数组，没有用map来存节点的子节点。
代码：
go：
代码语言：javascript复制type Trie struct {
IsWord bool
Children [26]*Trie
}
/** Initialize your data structure here. */
func Constructor() Trie {
return Trie{
IsWord : false,
Children: [26]*Trie{},
}
}
/** Inserts a word into the trie. */
func (this *Trie) Insert(word string) {
cur := this
for i:=0; i<len(word); i {
c := rune(word[i])
if cur.Children[c - 'a'] == nil {
newNode := Constructor()
cur.Children[c - 'a'] = &newNode
}
cur = cur.Children[c - 'a']
}
cur.IsWord = true
}
/** Returns if the word is in the trie. */
func (this *Trie) Search(word string) bool {
cur := this
for i:=0; i<len(word); i {
c := rune(word[i])
if cur.Children[c - 'a'] == nil {
return false
}
cur = cur.Children[c - 'a']
}
return cur.IsWord
}
/** Returns if there is any word in the trie that starts with the given prefix. */
func (this *Trie) StartsWith(prefix string) bool {
cur := this
for i := 0; i < len(prefix); i {
c := rune(prefix[i])
if cur.Children[c - 'a'] == nil {
return false
}
cur = cur.Children[c - 'a']
}
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);
*/
