算法系列：前缀树（字典树）_字典树前缀总和

前言

本篇归纳前缀树

前缀树

Trie，也称为字典树
一颗前缀树如下

• 树节点：树的节点中存放的是状态，判断字符串是否走到结尾了
• 边：每个边上有一个字符，从根开始的路径上的字符组成了串

一个前缀树的实现如下
包含 insert， search 和 startsWith 三个操作

from collections import defaultdict
class TrieNode: #节点构造
    def __init__(self):
        self.children = defaultdict(TrieNode)
        self.word = False

class Trie:
    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.root = TrieNode()

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

    def search(self, word: str) -> bool:
        """
        Returns if the word is in the trie.
        """
        tmp = self.root
        for a in word:
            if a not in tmp.children:
                return False
            tmp = tmp.children[a]
        if tmp.word:
            return True
        return False

    def startsWith(self, prefix: str) -> bool:
        """
        Returns if there is any word in the trie that starts with the given prefix.
        """
        tmp = self.root
        for a in prefix:
            if a not in tmp.children:
                return False
            tmp = tmp.children[a]
        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
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
'
运行
运行

下面看些实例

添加与搜索单词

leet上211题

如果数据结构中有任何与word匹配的字符串，则bool search（word）返回true，否则返回false。 
单词可能包含点“。” 点可以与任何字母匹配的地方。
请你设计一个数据结构，支持 添加新单词 和 查找字符串是否与任何先前添加的字符串匹配 。
实现词典类 WordDictionary ：
	WordDictionary() 初始化词典对象
	void addWord(word) 将 word 添加到数据结构中，之后可以对它进行匹配
	bool search(word) 如果数据结构中存在字符串与 word 匹配，则返回 true ；否则，返回  false 。word 中可能包含一些 '.' ，每个 . 都可以表示任何一个字母。
1
2
3
4
5
6
7

写法1

class WordDictionary:
    def __init__(self):
        """
        Initialize your data structure here.
        """
        from collections import defaultdict
        self.lookup = {}
        
    def addWord(self, word: str) -> None:
        """
        Adds a word into the data structure.
        """
        tree = self.lookup
        for a in word:
            tree = tree.setdefault(a, {})
        tree["#"] = {}
        
    def search(self, word: str) -> bool:
        """
        Returns if the word is in the data structure. A word could contain the dot character '.' to represent any one letter.
        """  
        def helper(word, tree):
            if not word:
                if "#" in tree:
                    return True
                return False
            if word[0] == ".":
                for t in tree:
                    if helper(word[1:], tree[t]):
                        return True
            elif word[0] in tree:
                if helper(word[1:], tree[word[0]]):
                    return True
            return False
        return helper(word, self.lookup)
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
'
运行
运行

写法2

from collections import defaultdict
class TrieNode: #节点构造
    def __init__(self):
        self.children = defaultdict(TrieNode)
        self.flag = False

class WordDictionary:

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

    def addWord(self, word: str) -> None:
        tmp = self.root
        for a in word:
            tmp = tmp.children[a]
        tmp.flag = True

    def search(self, word: str) -> bool:
        def helper(word, node):
            for i, w in enumerate(word):
                if w == ".":
                    for k in node.children:
                        if helper(word[i+1:], node.children[k]):
                            return True
                    return False
                else: 
                    node = node.children[w]
            return node.flag
            return False 
        return helper(word, self.root)
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
'
运行
运行

回文对

leet上336题

给定一组 互不相同 的单词， 找出所有不同 的索引对(i, j)
使得列表中的两个单词， words[i] + words[j] ，可拼接成回文串
1
2

from collections import defaultdict
class TrieNode: #节点构造
    def __init__(self):
        self.children = defaultdict(TrieNode)
        self.word = "#"

class Trie:
    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.root = TrieNode()

    def insert(self, word: str, idx: int) -> None:
        """
        Inserts a word into the trie.
        """
        tmp = self.root
        for a in word:
            tmp = tmp.children[a]
        tmp.word = idx

    def search(self, word: str) -> bool:
        """
        Returns if the word is in the trie.
        """
        tmp = self.root
        for a in word:
            if a not in tmp.children:
                return -1
            tmp = tmp.children[a]
        if tmp.word != "#":
            return tmp.word
        return -1

class Solution:
    def palindromePairs(self, words: List[str]) -> List[List[int]]:
        def is_palindrome(s):
            return s == s[::-1]

        trie = Trie()
        for i, w in enumerate(words):
            trie.insert(w, i)

        res = []
        for k, word in enumerate(words):
            n = len(word)
            for j in range(n + 1):
                pref = word[:j]
                suf = word[j:]
                if is_palindrome(pref):
                    back = suf[::-1]
                    idx = trie.search(back)
                    if back != word and idx != -1:
                        res.append([idx, k])
                if j != n and is_palindrome(suf):
                    back = pref[::-1]
                    idx = trie.search(back)
                    if back != word and idx != -1:
                        rse.append([k, idx])
        return res
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
55
56
57
58
59
60
61

数组中两个数的最大异或值

leet上421题

给定一个非空数组，数组中元素为 a0, a1, a2, … , an-1，其中 0 ≤ ai < 231
找到 ai 和aj 最大的异或 (XOR) 运算结果，其中0 ≤ i,  j < n
1
2

from collections import defaultdict
class TrieNode:
    def __init__(self):
        self.children = defaultdict(TrieNode)
        self.flag = False

class Trie:
    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.root = TrieNode()

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

    def search(self, word: str) -> bool:
        """
        Returns if the word is in the trie.
        """
        node = self.root
        res = ""
        for a in word:
            tmp = str(1^int(a))
            if tmp in node.children:
                node = node.children[tmp]
                res += tmp
            else:
                node = node.children[a]
                res += a
        return res

class Solution:
    def findMaximumXOR(self, nums: List[int]) -> int:
        trie = Trie()
        l = list(map(lambda x: bin(x)[2:].zfill(32), nums))
        for num in l:
            trie.insert(num)
        res = float("-inf")
        for num in l:
            res = max(res, int(num, 2) ^ int(trie.search(num), 2))
        return res

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

单词替换

leet上648题

在英语中，我们有一个叫做 词根(root)的概念，它可以跟着其他一些词组成另一个较长的单词——我们称这个词为 继承词(successor)
例如，词根an，跟随着单词 other(其他)，可以形成新的单词 another(另一个)
现在，给定一个由许多词根组成的词典和一个句子
你需要将句子中的所有继承词用词根替换掉。如果继承词有许多可以形成它的词根，则用最短的词根替换它
你需要输出替换之后的句子
1
2
3
4
5

from collections import defaultdict
class TrieNode: #节点构造
    def __init__(self):
        self.children = defaultdict(TrieNode)
        self.flag = False

class Trie:
    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.root = TrieNode()

    def insert(self, word: str) -> None:
        """
        Inserts a word into the trie.
        """
        tmp = self.root
        for a in word:
            tmp = tmp.children[a]
        tmp.flag = True

    def search(self, word: str) -> bool:
        """
        Returns if the word is in the trie.
        """
        tmp = self.root
        for a in word:
            if a not in tmp.children:
                return False
            tmp = tmp.children[a]
        if tmp.flag:
            return True
        return False

class Solution:
    def replaceWords(self, dictionary: List[str], sentence: str) -> str:
        trie = Trie()
        for word in dictionary:
            trie.insert(word)
        l = sentence.split(" ")
        for i in range(len(l)):
            for j in range(1, len(l[i])):
                if trie.search(l[i][:j]):
                    l[i] = l[i][:j] 
        return " ".join(l)
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

键值映射

leet上677题

实现一个 MapSum 类里的两个方法，insert 和 sum。
对于方法 insert，你将得到一对（字符串，整数）的键值对。字符串表示键，整数表示值。如果键已经存在，那么原来的键值对将被替代成新的键值对。
对于方法 sum，你将得到一个表示前缀的字符串，你需要返回所有以该前缀开头的键的值的总和。
1
2
3

from collections import defaultdict
class TrieNode:
    def __init__(self):
        self.children = defaultdict(TrieNode)
        self.val = 0

class MapSum:
    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.root = TrieNode()
        
    def insert(self, key: str, val: int) -> None:
        node = self.root
        path = [node]
        for char in key:
            node = node.children[char]
            path.append(node)
        diff = node.val - sum([child.val for child in node.children.values()])
        for node in path:
            node.val += val - diff

    def sum(self, prefix: str) -> int:
        node = self.root
        for char in prefix:
            node = node.children[char]
        return node.val
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
'
运行
运行

字符流

leet上1032题

按下述要求实现 StreamChecker 类：
StreamChecker(words)：构造函数，用给定的字词初始化数据结构。
query(letter)：如果存在某些 k >= 1，可以用查询的最后 k个字符（按从旧到新顺序，包括刚刚查询的字母）拼写出给定字词表中的某一字词时，返回 true。否则，返回 false
1
2
3

写法1

class Trie:

    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.Trie = {}

    def insert(self, word):
        """
        Inserts a word into the trie.
        :type word: str
        :rtype: void
        """
        curr = self.Trie
        for w in word:
            if w not in curr:
                curr[w] = {}
            curr = curr[w]
        curr['#'] = 1

    def search(self, word):
        """
        Returns if the word is in the trie.
        :type word: str
        :rtype: bool
        """
        curr = self.Trie
        for w in word:
            if w not in curr:
                return False
            if "#" in curr[w]:
                return True
            curr = curr[w]
        return False


class StreamChecker:

    def __init__(self, words: List[str]):
        self.trie = Trie()
        self.stream = deque([])

        for word in set(words):
            self.trie.insert(word[::-1])

    def query(self, letter: str) -> bool:
        self.stream.appendleft(letter)
        return self.trie.search(self.stream)

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

写法2

from collections import defaultdict
class TrieNode:
    def __init__(self):
        self.children = defaultdict(TrieNode)
        self.flag = False

class Trie:
    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.root = TrieNode()

    def insert(self, word: str) -> None:
        """
        Inserts a word into the trie.
        """
        tmp = self.root
        for a in word:
            tmp = tmp.children[a]
        tmp.flag = True

    def search(self, word: str) -> bool:
        """
        Returns if the word is in the trie.
        """
        tmp = self.root
        for a in word:
            if a not in tmp.children:
                return False
            tmp = tmp.children[a]
            if tmp.flag:
                return True
        return False

class StreamChecker:

    def __init__(self, words: List[str]):
        self.trie = Trie()
        self.stream = deque([])

        for word in set(words):
            self.trie.insert(word[::-1])

    def query(self, letter: str) -> bool:
        self.stream.appendleft(letter)
        return self.trie.search(self.stream)
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

结语

前缀树是很有用很秀的算法