// Trie字典树 https://blog.csdn.net/rxbook/article/details/130983299
package main

import (
	"fmt"
)

// Trie树结构体
type TrieNode struct {
	Data  byte               //存储字符数据
	Next  map[byte]*TrieNode //下一个节点指针
	IsEnd bool               //是否到达叶子结点
}

// Trie树根节点
type TrieRoot struct {
	Len  int //字符个数
	Node map[byte]*TrieNode
}

// 初始化一个Trie树,并给根节点赋值
func NewTire() TrieRoot {
	tRoot := TrieRoot{
		Len:  0,
		Node: make(map[byte]*TrieNode),
	}
	return tRoot
}

// 插入字符
func (tn *TrieRoot) insert(str string) {
	cur := tn.Node
	//循环遍历单词的每个字符
	for i := 0; i < len(str); i++ {
		if cur[str[i]] == nil {
			newNode := &TrieNode{
				Data:  str[i],
				Next:  make(map[byte]*TrieNode),
				IsEnd: false,
			}
			cur[str[i]] = newNode
		}
		//判断是否到达叶子结点
		if i == len(str)-1 {
			cur[str[i]].IsEnd = true
		}
		cur = cur[str[i]].Next
	}
	tn.Len++
}

// 查找字符
func (tn *TrieRoot) find(str string) bool {
	if tn.Node == nil {
		return false
	}
	cur := tn.Node
	//循环遍历单词的每个字符
	for i := 0; i < len(str); i++ {
		//如果某个字符不存在，直接返回false
		if cur[str[i]] == nil {
			return false
		}
		if cur[str[i]].Data != str[i] {
			return false
		}
		if i == len(str)-1 {
			//判断最后一个比较的字符是否到达叶子结点,如果不需要精确匹配就去掉这个判断
			if cur[str[i]].IsEnd == true {
				return true
			}
		}
		cur = cur[str[i]].Next
	}
	return false
}

func main() {
	tire := NewTire()
	tire.insert("city")
	tire.insert("cat")
	tire.insert("car")
	tire.insert("door")
	tire.insert("dog")
	tire.insert("deep")
	fmt.Println("字符串数量：", tire.Len) //6

	fmt.Println(tire.find("cat")) //true
	fmt.Println(tire.find("ca"))  //false,因为是精确匹配
	fmt.Println(tire.find("cd"))  //false
}