字典树

字典树又叫前缀树、单词查找树，树形结构，是哈希树的变种。能够统计、排序和保存大量的字符串，经常被搜索引擎系统用于文本词频统计。优点是利用字符串的公共前缀来减少查询时间，最大程度减少无谓字符串的比较，查询效率高于哈希树。

字典树的原理是这样的，假设我现在有一些字符串["a","ab","abc","abcd"]，它们的特点是具有公共前缀，适合使用树形数据结构保存，从根节点到叶子结点的一条路径就能保存所有具有公共前缀的单词。

使用Python实现非常简单，考虑到删除操作涉及较少，暂不实现，简洁版代码如下：

class TreeNode(object):
    def __init__(self):
        self.nodes = {}         # 记录当前结点的子结点
        self.is_leaf = False   # 当前结点是否表示一个单词
        self.count = 0          # 单词树中单词的总量

    def insert(self,word):
        curr = self
        for c in word:
            if not curr.nodes.get(c,None):
                new_node = TreeNode()
                curr.nodes[c] = new_node
            curr = curr.nodes[c]
        curr.is_leaf = True
        self.count += 1
        return

    def insert_many(self,words):
        for word in words:
            self.insert(word)
        return

    def search(self,word):
        curr = self
        try:
            for c in word:
                curr = curr.nodes[c]
        except:
            return False
        return curr.is_leaf

问题实战

分词问题

给定一个字符串s，和一个词典Dict。对字符串s基于词典dict进行分词，存在包含情况的按最长的分词。

输入s=cde ab abc cde gf

dict=["abc" ,"abd","cde","abc cde","abc abd"]

输出s=#cde#  ab  #abc cde#  gf

解决本题要点如下：

• 将词典构建字典树
• 遍历字符串，将每个单词插入字典树，并记录满足题目要求的最长单词
• 在遍历的过程中，如果已经出现前缀缺失，及时剪枝

词典中最长单词

解决本题要点如下：

• 对字符串数组排序，构建字典树
• 遍历数组，将每个单词插入字典树，并记录满足题目要求的最长单词
• 在遍历的过程中，如果已经出现前缀缺失，及时剪枝

单词替换

本题要点如下：

• 使用字典树保存词根
• 将 sentence 切割为单词，保存在数组中
• 遍历数组中的单词，如果访问至叶子结点(is_leaf == True)，证明单词具有该词根，将其替换