208 实现 Trie (前缀树)

题目描述#

Trie（发音类似 “try”）或者说 前缀树 是一种树形数据结构，用于高效地存储和检索字符串数据集中的键。这一数据结构有相当多的应用情景，例如自动补全和拼写检查。

请你实现 Trie 类：

Trie() 初始化前缀树对象。
void insert(String word) 向前缀树中插入字符串 word。
boolean search(String word) 如果字符串 word 在前缀树中，返回 true（即，在检索之前已经插入）；否则，返回 false。
boolean startsWith(String prefix) 如果之前已经插入的字符串 word 的前缀之一为 prefix，返回 true；否则，返回 false。

思路#

前缀树的核心思想是：把公共前缀的字符在树上共享同一条路径，每个节点代表到达该节点所经过的字符序列。

每个节点维护两个信息：

child [26]*Node：26 个小写字母对应的子节点指针，用数组下标 v - 'a' 直接索引，O(1) 定位。
isEnd bool：标记从根到当前节点的字符序列是否构成一个完整的单词。这一标记是区分 search 和 startsWith 的关键 —— 前者必须走到完整单词的结尾，后者只要路径存在即可。

三个操作都是沿着 word/prefix 的字符顺序从根向下走：

Insert：路径上缺少的节点就新建，走到末尾把 isEnd 置为 true。
Search：路径中途有缺失就返回 false，完整走完后看最后一个节点的 isEnd。
StartsWith：路径中途缺失就返回 false，走完就返回 true，不看 isEnd。

思维边界#

不要把 search 和 startsWith 写成一个函数：判断末尾 isEnd 是前者独有的语义。
child 用定长数组 [26]*Node 是因为题目限定小写字母；若是任意字符集，应改用 map[rune]*Node。

代码#

type Trie struct {
    root *Node
}

type Node struct {
    child [26]*Node
    isEnd bool
}

func Constructor() Trie {
    return Trie{
        root: &Node{},
    }
}

func (this *Trie) Insert(word string) {
    cur := this.root
    for _, v := range word {
        index := v - 'a'
        if cur.child[index] == nil {
            cur.child[index] = &Node{}
        }
        cur = cur.child[index]
    }
    cur.isEnd = true
}

func (this *Trie) Search(word string) bool {
    cur := this.root
    for _, v := range word {
        index := v - 'a'
        if cur.child[index] == nil {
            return false
        }
        cur = cur.child[index]
    }
    return cur.isEnd
}

func (this *Trie) StartsWith(prefix string) bool {
    cur := this.root
    for _, v := range prefix {
        index := v - 'a'
        if cur.child[index] == nil {
            return false
        }
        cur = cur.child[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);
 */