# Leetcode - Implement Trie (Prefix Tree)

violet posted @ Mar 27, 2020 06:59:00 AM in 算法 with tags Algorithm Golang Trie , 41 阅读

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.

```type Trie struct {
Children []*Trie
Leaf bool
}

/** Initialize your data structure here. */
func Constructor() Trie {
return Trie{
Children: make([]*Trie, 26),
},
}
}

/** Inserts a word into the trie. */
func (this *Trie) Insert(word string)  {
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 {
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 {
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);
*/```

(输入验证码)
or Ctrl+Enter