0208. Implement Trie Prefix Tree

# 208. 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.

## 解题思路 #

• 要求实现一个 Trie 的数据结构，具有 `insert``search`, `startsWith` 三种操作
• 这一题就是经典的 Trie 实现。本题的实现可以作为 Trie 的模板。

## 代码 #

``````
package leetcode

type Trie struct {
isWord   bool
children map[rune]*Trie
}

/** Initialize your data structure here. */
func Constructor208() Trie {
return Trie{isWord: false, children: make(map[rune]*Trie)}
}

/** Inserts a word into the trie. */
func (this *Trie) Insert(word string) {
parent := this
for _, ch := range word {
if child, ok := parent.children[ch]; ok {
parent = child
} else {
newChild := &Trie{children: make(map[rune]*Trie)}
parent.children[ch] = newChild
parent = newChild
}
}
parent.isWord = true
}

/** Returns if the word is in the trie. */
func (this *Trie) Search(word string) bool {
parent := this
for _, ch := range word {
if child, ok := parent.children[ch]; ok {
parent = child
continue
}
return false
}
return parent.isWord
}

/** Returns if there is any word in the trie that starts with the given prefix. */
func (this *Trie) StartsWith(prefix string) bool {
parent := this
for _, ch := range prefix {
if child, ok := parent.children[ch]; ok {
parent = child
continue
}
return false
}
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);
*/

``````

Sep 6, 2020