[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 = False

class 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 = False

class 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. 恢复空格,力扣官方题解