前缀树也叫字典树或排序树（trie tree）。

定义：

一棵保存了某个单词集合的树称为字典树。连接一个节点及其子节点的弧线用不同字母标注。因此，字典中的每个单词与树中从根节点到树节点的路径相关。每个节点都是标记，特殊标记用于区分相关字母组合究竟是字典中的单词，还是字典中单词的前缀。

其特点是：用边表示字符，当走到叶子结点的时候，沿途所经过的边组成了一个字符串。其优点是：利用字符串的公共前缀来减少查询时间，最大限度地减少无谓的字符串比较，查询效率比哈希表高。

以下是根据题目示例："bad"、"dad"、"mad" 组件的 Trie 树，结点值为“1” 表示这是一个单词的结尾。

应用：

如何把单词存入一个字典来纠正拼写呢？对于某个给定的单词，我们希望很快在字典中找到一个最接近的词。如果把字典里的所有单词存在一个散列表里，单词之间的一切相近性信息都将丢失。所以，更好的方式是把这些单词存入字典树。

拼写纠正： 利用上述数据结构，我们很容易在字典中找到一个与给定单词距离为 dist 的单词。这里的距离以 编辑距离（levenshtein distance）来定义[1]。

1. lc 208 - 实现 Trie (前缀树)

  • 题目来源
  • 实现一个 Trie (前缀树)，包含 insert, search, 和 startsWith 这三个操作。
  • 难度：中等

1.1 解题思路 - 哈希表

我们要构建一个空根节点,节点迭代到下一个节点。用到哈希表，key为字符，value为另一个哈希表，储存单词中字符的后一个字符，从而构建树。

单词结尾，用一个特殊字符终止。

当从根节点遍历这个树，单词的字符依次出现，代表找到了这个前缀。

1.2 时间复杂度

插入：

  • 时间复杂度： O(m)。 其中 m 为键长。在算法的每次迭代中，我们要么检查要么创建一个节点，直到到达键尾。只需要 m 次操作。
  • 空间复杂度： O(m)。最坏的情况下，连续插入m空子字典。

查找：

  • 时间复杂度： O(m)。 算法的每一步均搜索下一个键字符。
  • 空间复杂度： O(1)。

1.3 代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
class Trie:

    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.lookup = dict() # 相当于空根节点


    def insert(self, word: str) -> None:
        """
        Inserts a word into the trie.
        """
        tree = self.lookup
        for a in word:
            if a not in tree:
                tree[a] = dict()
            tree = tree[a] # a not in tree时，也要执行这句，推进树
        # 单词结束标志
        tree['@'] = '@'


    def search(self, word: str) -> bool:
        """
        Returns if the word is in the trie.
        """
        return self.startsWith(word+'@') # 不要忘记return，否则返回不了`bool`


    def startsWith(self, prefix: str) -> bool:
        """
        Returns if there is any word in the trie that starts with the given prefix.
        """
        tree = self.lookup
        for a in prefix:
            if a not in tree:
                return False
            tree = tree[a] # a not in tree时，也要执行这句，推进树
        return True



# Your Trie object will be instantiated and called as such:
# obj = Trie()
# obj.insert(word)
# param_2 = obj.search(word)
# param_3 = obj.startsWith(prefix)

1.4 解疑

  1. tree = tree[a]如何理解？

答：【一个不错的网友评论】lookup的key是字符，value是另一个字典，每一个字典就相当于树的节点，tree=tree[a]相当于把指针移到下一个字符所在的节点。

比如说先插入一个单词 word ，我们在建立树的时候会给w先建立一个字典，这个字典就是以w为前缀的所有单词的字典，接下来遍历到字母o的时候，给o再建立一个字典，这个o的字典就是刚才建立的w的字典的子字典。这样一层一层把单词的每个字母都存放到所属字母的子字典中去。之所以要tree = tree[a]就是要顺着要查询的单词的每一个字母，一层一层跳进子字典里：

1
2
3
4
5
6
7
    e - e - k (以w为首的一个其他单词:week)
 /
w - o - r - d  (以w为首的一个单词:word)
 \   \ 
   \    - a - h (以wo为首的一个其他单词:woah)
     \
       a - l - m - a -r - t (以w为首的一个其他单词:walmart)
  1. tree = self.lookup。 这个地方没理解， 为什么对 tree 操作会把self.lookup 也修改。 看了别的答案是 另外构造一个Node类， 如果不存在，就创建一个 Node类， 你这个直接 tree = tree[a] 应该怎么去理解？

答：这是python的一个特性，浅复制，a是一个列表，b=a，接着对b所有的操作都会在a上也操作一次，就跟劫的影分身似的，如果不想这样，想让b，a没有关联就得import copy.deepcopy。

python里面, list, dict, set都是可变类型的，int, string,tuple是不可变类型，比如t1 = t2 = {'a':1, 'b':2}里面t1,t2指向同一个内存地址:id(t1) = id(t2)， t1.update(b=2)之后t2跟着改变，因为t1修改了同一个内存地址的数据；但是如果t1=t2=100, t2+=200，那么t1还是100，而且t1,t2指向不同的内存地址了；

2. lc 211 - 添加与搜索单词 - 数据结构设计

  • 题目来源
  • 请你设计一个数据结构，支持 添加新单词 和 查找字符串是否与任何先前添加的字符串匹配 。
  • 实现词典类 WordDictionary ： WordDictionary() 初始化词典对象 void addWord(word) 将 word 添加到数据结构中，之后可以对它进行匹配 bool search(word) 如果数据结构中存在字符串与 word 匹配，则返回 true ；否则，返回  false 。word 中可能包含一些 '.' ，每个 . 都可以表示任何一个字母。
  • 提示： 1 <= word.length <= 500 addWord 中的 word 由小写英文字母组成 search 中的 word 由 '.' 或小写英文字母组成 最调用多 50000 次 addWord 和 search
  • 难度：中等

一个结点指向孩子结点的“指针”（一般情况下多于 1 个），可以使用数组表示，也可以使用哈希表表示

2.1 解题思路 - 哈希表

关于这道问题的难点是通配符 "." 的处理，其实也不难：在遇到 "." 的时候，使用递归方法，将该结点的每一个分支都看过去，只要有一个分支返回 true 就可以了，全部分支都走过去，都没有返回 true 的才返回 false[1]。

2.2 时间复杂度

插入：

  • 时间复杂度： O(m)。 其中 m 为键长。在算法的每次迭代中，我们要么检查要么创建一个节点，直到到达键尾。只需要 m 次操作。
  • 空间复杂度： O(m)。最坏的情况下，连续插入m空子字典。

查找：

  • 时间复杂度： O(m)。 算法的每一步均搜索下一个键字符。
  • 空间复杂度： O(1)。

2.3 代码

细节问题很多，需要多写几遍，特别是递归内部和addword中字符的迭代。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
class WordDictionary(object):
    class Node:
        def __init__(self): 
            self.isWord = False
            self.next = dict()

    def __init__(self):
        """
        Initialize your data structure here.
        """ 
        self.root = WordDictionary.Node()
        

    def addWord(self, word):
        """
        Adds a word into the data structure.
        :type word: str
        :rtype: void
        """ 
        cur_node = self.root
        for a in word:
            if a not in cur_node.next:
                cur_node.next[a] = WordDictionary.Node() # 不要写成 = cur_node.next.next 

            cur_node = cur_node.next[a]
        if not cur_node.isWord:
            cur_node.isWord = True


    def search(self, word):
        """
        Returns if the word is in the data structure. A word could contain the dot character '.' to represent any one letter.
        :type word: str
        :rtype: bool
        """  
        # 注意：这里要设置辅助函数
        return self.recursion(self.root,word,0)

    def recursion(self, node, word, index):
        if index == len(word):
            return node.isWord
        a = word[index]
        if a == '.':
            for next in node.next:
                if self.recursion(node.next[next],word,index+1): # node.next[next]不要写错
                    return True
            # 注意：这里要返回，不返回的话，就会出现`self.recursion(node.next[next],word,index+1)`返回false时，没有返回值，最终输出null的错误
            return False
        else:
            # 注意：这里要使用 else
            if a not in node.next:
                return False
            # 注意：这里要使用 return 返回
            return self.recursion(node.next[a],word,index+1)

树的遍历迭代写法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
    def search(self, word):

        stack = [(self.root, word)]
        while stack:
            node, w = stack.pop()
            if not w:
                if node.isWord:
                    return True
            elif w[0] == '.':
                for c in node.next.values():
                    stack.append([c,w[1:]])
            elif w[0] in node.next:
                stack.append([node.next[w[0]], w[1:]])

        return False

作者：davd18596
链接：https://leetcode-cn.com/leetbook/read/programmation-efficace/91r0dr/?discussion=DvzqFJ

参考

[1] 图灵教育. 2.3 使用字典树进行拼写纠正. https://leetcode-cn.com/leetbook/read/programmation-efficace/94bas5/

[2] liweiwei1419. 遇到通配符时递归处理（Python 代码、Java 代码). https://leetcode-cn.com/problems/design-add-and-search-words-data-structure/solution/yu-dao-tong-pei-fu-shi-di-gui-chu-li-python-dai-ma/