Leetcode-208. 实现Trie（前缀树）

前缀树是一个由“路径”和“节点”组成多叉树结构。由根节点出发，按照存储字符串的每个字符，创建对应字符路径，以此实现快速查找单词或是否为前缀的功能。

此题要求简单，只需实现下面几种功能：

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

因此有简单的实现方法。

package main

import "fmt"

type Trie struct {
	//结束标志
	isEnd    bool
	//子节点使用大小为26的数组存储
	children [26]*Trie
}

func Constructor() Trie {
	return Trie{}
}

//插入节点
func (this *Trie) Insert(word string) {
	node := this

	//遍历单词，确定依次向下的节点
	for _, ch := range word {
		//确定路径位置，即应该放到数组哪个位置
		path := ch - 'a'
		if node.children[path] == nil {
			//若不存在这个位置，则创建
			node.children[path] = &Trie{}
		}
		//向下移动
		node = node.children[path]
	}
	//结尾标志置位true
	node.isEnd = true
}

//搜索前缀
func (this *Trie) SearchPrefix(prefix string) *Trie {
	node := this
	for _, ch := range prefix {
		path := ch - 'a'
		if node.children[path] == nil {
			return nil
		}
		node = node.children[path]
	}
	return node
}

//若能找到前缀并且isEnd为true，则找到这个单词
func (this *Trie) Search(word string) bool {
	node := this.SearchPrefix(word)
	return node != nil && node.isEnd
}

func (this *Trie) StartsWith(prefix string) bool {
	return this.SearchPrefix(prefix) != nil
}

func main() {
	T := Constructor()

	T.Insert("hello")
	T.Insert("how")
	T.Insert("heihei")

	if ok := T.Search("how"); ok {
		fmt.Println("成功找到")
	} else {
		fmt.Println("meiyou找到")
	}
}

通用实现：

明天写，回寝室喽