Golang实现字典树，寻找公共前缀的字符串

字典树可以用来解决搜索前缀问题
例如给若干个不同长度的字符串
找出有公共前缀的字符串有几个
面试遇到的

或者计算身份证号，同样前缀的身份证号有多少个
之前牛客模考遇到的

此算法在搜索引擎中非常使用，写了前几个字就会弹出来相关搜索。
以及在存储大量有重复前缀的数据时可以节省大量空间。
查找的时间复杂度就是O（字符串长度）

本质上是个树，因此用链表链接。以下代码用字符串来表示，假设只有26个小写字母。

package main

import "fmt"

//结构体根据需要自行设置
type tree struct {
	isWord bool
	//用来标记当前位置是否为一个单词
	count  int
	//用来标记当前位置的前缀出现次数
	next   [26]*tree
	//每个位置都有26个子树
}

func main() {
	//实现一个字典树
	word := []string{"abcdef", "aeqweq", "abcjer", "abcdgh", "abcdgk", "aberqer", "abeqwe", "a"}
	//随便设了个例子
	root := &tree{}
	//初始化一个根节点，从根节点开始查找
	nroot := root
	//节点要移动，因此留一个备用头节点，每次遍历完恢复到头部位置
	for _, w := range word {
	//取出一个单词
		root = nroot
		//将节点移到头部
		for i := range w {
		//判断单词的每一个字符
			if root.next[w[i]-'a'] == nil {
				//如果这个字符在的节点为nil，说明这个字符第一次出现，则要给它初始化
				root.next[w[i]-'a'] = &tree{}
			}
			//给这个字符出现次数加1
			root.next[w[i]-'a'].count++
			if i == len(w)-1 {
			//如果当前字符是该字母的最后一个字符了，就标记此前缀是一个单词
				root.next[w[i]-'a'].isWord = true
			}
			//移动到当前字符，重复下一个字符操作
			root = root.next[w[i]-'a']
		}
	}
	//初始化完成，下面是查询操作
	root = nroot
	//移动到头节点
	query := "abc"
	//设一个查询的前缀
	for i := range query {
	//如果遍历过程中 字符不存在就提前退出，输出不存在
		if root.next[query[i]-'a'] == nil {
			fmt.Println("not exist")
			break
		}
		//不然就移动到下一个字符
		root = root.next[query[i]-'a']
		//直到移动到了前缀的最后一个字符，就输出结果
		if i == len(query)-1 {
			fmt.Println("以", query, "开头的单词有", root.count, "个")
			fmt.Println(query, "is a word?", root.isWord)
		}
	}
}