[leetcode刷题笔记]Trie字典树

在刷题中遇到trie字典树数据结构，于是对trie做了学习，并找来相关例题。本文记录LeetCode刷题少量知识点，水平有限还望多多指正

恢复空格

哦，不！你不小心把一个长篇文章中的空格、标点都删掉了，并且大写也弄成了小写。像句子”I reset the computer. It still didn’t boot!”已经变成了”iresetthecomputeritstilldidntboot”。在解决标点符号和大小写之前，你得先把它断成词语。当然了，你有一本厚厚的词典dictionary，不过，有些词没在词典里。假设文章用sentence表示，设计一个算法，把文章断开，要求未识别的字符最少，返回未识别的字符数。

输入：
dictionary = [“looked”,”just”,”like”,”her”,”brother”]
sentence = “jesslookedjustliketimherbrother”
输出： 7

解法：Trie字典树+dp动态规划
首先详情一下字典树

Trie字典树主要用于存储字符串，Trie 的每个 Node 保存一个字符。用链表来形容的话，就是一个字符串就是一个链表。每个Node都保存了它的所有子节点。
例如我们往字典树中插入see、pain、paint三个单词，Trie字典树如下所示：

也就是说假如只考虑小写的26个字母，那么Trie字典树的每个节点都可能有26个子节点。

本文是使用链表来实现Trie字典树，字符串的每个字符作为一个Node节点，Node主要有两部分组成：

• 能否是单词 (is_word)
• 节点所有的子节点，用字典来保存 (child)

class TreeNode:    def __init__(self):        self.child = {}        self.is_word = False

构建 单词的最后一个字符的节点的 is_word 设置为 true，节点的所有子节点，通过一个字典来存储，key是当前子节点对应的字符，value是子节点。在本题中，通过dictionary构建Trie Tree。

    def make_tree(self, dictionary):        for word in dictionary:            node = self.root            for s in word:                if not s in node.child:                    node.child[s] = TreeNode()                node = node.child[s]            node.is_word = True

在本题中用到了动态规划，定义 dp[i] 表示考虑前 i 个字符最少的未识别的字符数量，从前往后计算 dp 值。考虑转移方程，每次转移的时候我们考虑第 j(j≤i) 个到第 i 个字符组成的子串 sentence[j−1⋯i−1] 能否能在词典中找到，假如能找到的话按照定义转移方程即为

否则没有找到的话我们可以复用 dp[i−1] 的状态再加受骗前未被识别的第 i 个字符，因而此时 dp 值为

完整代码为

class TreeNode:    def __init__(self):        self.child = {}        self.is_word = Falseclass Solution:      def make_tree(self, dictionary):        for word in dictionary:            node = self.root            for s in word:                if not s in node.child:                    node.child[s] = TreeNode()                node = node.child[s]            node.is_word = True    def respace(self, dictionary: List[str], sentence: str) -> int:        self.root = TreeNode()        self.make_tree(dictionary)        n = len(sentence)        dp = [0] * (n + 1)        for i in range(n-1, -1, -1):            dp[i] = n - i            node = self.root            for j in range(i, n):                c = sentence[j]                if c not in node.child:                    dp[i] = min(dp[i], dp[j+1]+j-i+1)                    break                if node.child[c].is_word:                    dp[i] = min(dp[i], dp[j+1])                else:                    dp[i] = min(dp[i], dp[j+1]+j-i+1)                node = node.child[c]        return dp[0]

再来看其余几道Trie题目。

实现 Trie (前缀树)

实现一个 Trie (前缀树)，包含 insert, search, 和 startsWith 这三个操作。

Trie trie = new Trie();

trie.insert("apple");
trie.search("apple"); // 返回 true
trie.search("app"); // 返回 false
trie.startsWith("app"); // 返回 true
trie.insert("app");
trie.search("app"); // 返回 true

class TreeNode:    def __init__(self):        self.child = defaultdict(TreeNode)        self.is_word = Falseclass Trie:    def __init__(self):        """        Initialize your data structure here.        """        self.root = TreeNode()

添加将单词中字目依次增加到树中，并将最后一个字母is_word设定为true。若字母存在，如apple与app，则便利后的最后一个字母为true。

    def insert(self, word: str) -> None:        """        Inserts a word into the trie.        """        node = self.root        for s in word:            node = node.child[s]        node.is_word = True

查找比较简单，只要从根一次向下查找，找到最后一个字母所在节点的is_word能否为true。若无法遍历完单词，则查找结果为false。

    def search(self, word: str) -> bool:        """        Returns if the word is in the trie.        """        node = self.root        for s in word:            node = node.child[s]            if not node:                return False        return node.is_word    def startsWith(self, prefix: str) -> bool:        """        Returns if there is any word in the trie that starts with the given prefix.        """        node = self.root        for s in prefix:            node = node.child[s]            if not node:                return False        return True

Reference

1. 数据结构与算法（十一）Trie字典树,Chiclaim
2. 恢复空格,力扣官方题解