tire（2）实现关键字联想

前缀树(Trie)是一种树形结构，用于存储和查询字符串。它可以高效地维护一个大量的字符串，并支持一些常用的操作，如查询前缀、插入、删除等。

在实现前缀树时，我们需要定义一个结构体来表示树中的节点，每个节点需要有指向子节点的指针和表示该节点对应字符的字符变量。

具体实现如下：

package trie

type TrieNode struct {
    children map[rune]*TrieNode
    isEnd    bool
}

type Trie struct {
    root *TrieNode
}

func (t *Trie) Insert(word string) {
    node := t.root
    for _, char := range word {
        if _, ok := node.children[char]; !ok {
            node.children[char] = &TrieNode{children: make(map[rune]*TrieNode)}
        }
        node = node.children[char]
    }
    node.isEnd = true
}

上面这段代码定义了一个Trie结构体，其中包含一个根节点root。Trie结构体还定义了一个Insert()函数，用于向前缀树中插入一个字符串。在插入时，遍历字符串中的每个字符，如果当前节点的子节点中不存在该字符，则新建一个子节点并将当前节点移动到该子节点。最后，将最后一个字符对应的节点的isEnd标记设为true表示该字符串已经插入到前缀树中。

对于关键词联想，可以在前缀树上实现一个查询函数，它将从当前前缀开始搜索，返回所有以该前缀开头的字符串。可以使用DFS算法来遍历前缀树并找到所有以该前缀开头的字符串。

具体实现如下：

func (t *Trie) Suggest(prefix string) []string {
    suggestions := make([]string, 0)
    node := t.root
    for _, char := range prefix {
        if _, ok := node.children[char]; !ok {
            return suggestions
        }
        node = node.children[char]
    }
    getSuggestions(node, prefix, &suggestions)
    return suggestions
}

func getSuggestions(node *TrieNode, prefix string, suggestions *[]string) {
    if node.isEnd {
        *suggestions = append(*suggestions, prefix)
    }
    for char, child := range node.children {
        getSuggestions(child, prefix+string(char), suggestions)
    }
}

上面这段代码定义了一个Trie的Suggest()函数，用于查询以给定前缀开头的所有字符串。首先，它会在前缀树上查找前缀，如果找不到，则直接返回空列表。否则，调用getSuggestions()函数来遍历前缀树，找到所有以该前缀开头的字符串。getSuggestions()函数使用DFS算法，如果当前节点是一个单词的结尾，则将该单词加入结果列表。它还将遍历该节点的子节点，并递归调用getSuggestions()函数。

可以先建立一个Trie结构体,然后使用Insert方法插入字符串到Trie中，接着使用Suggest()函数来查询以给定前缀开头的所有字符串

func main() {
    t := Trie{root: &TrieNode{children: make(map[rune]*TrieNode)}}
    t.Insert("fjndklsjflkds")
    t.Insert("fsdfs")
    t.Insert("fgggads")
    t.Insert("22233344")
    log.Println(t.Suggest("f"))
}