Open yankewei opened 3 years ago
这个在应用中还挺常见的,面试的时候也有很多人问这个
type Trie struct {
children [26]*Trie
isEnd bool
}
/** Initialize your data structure here. */
func Constructor() Trie {
return Trie{}
}
/** Inserts a word into the trie. */
func (this *Trie) Insert(word string) {
for _, v := range word {
if this.children[v-'a'] == nil {
this.children[v-'a'] = &Trie{}
}
this = this.children[v-'a']
}
this.isEnd = true
}
/** Returns if the word is in the trie. */
func (this *Trie) Search(word string) bool {
for _, v := range word {
if this.children[v-'a'] == nil {
return false
}
this = this.children[v-'a']
}
return this.isEnd
}
/** Returns if there is any word in the trie that starts with the given prefix. */
func (this *Trie) StartsWith(prefix string) bool {
for _, v := range prefix {
if this.children[v-'a'] == nil {
return false
}
this = this.children[v-'a']
}
return this != nil
}
/**
* 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);
*/
Trie(发音类似 "try")或者说 前缀树 是一种树形数据结构,用于高效地存储和检索字符串数据集中的键。这一数据结构有相当多的应用情景,例如自动补完和拼写检查。
请你实现 Trie 类:
示例:
提示:
来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/implement-trie-prefix-tree 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。