前缀树

前缀树

三月 05, 2022

前缀树

在python中 我们可以用字典嵌套的方法来构造一个树的结构

字典的key是每一个单词的字母 key所对应的value就再开阔一个字典 这样就可以一个字母接着一个字母进行嵌套 在单词的结尾加一个end 如果遍历到end说明检索成功(避免出现apple检索app成功的情况)

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
class Trie:

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


    def insert(self, word: str) -> None:
        """
        Inserts a word into the trie.
        """
        temp = self.dic
        for one in word:
            if one not in temp:
                temp[one] = {}
            temp = temp[one]
        temp['end'] = True


    def search(self, word: str) -> bool:
        """
        Returns if the word is in the trie.
        """
        temp = self.dic
        for one in word:
            if one not in temp:
                return False
            temp = temp[one]
        return 'end' in temp


    def startsWith(self, prefix: str) -> bool:
        """
        Returns if there is any word in the trie that starts with the given prefix.
        """
        temp = self.dic
        for one in prefix:
            if one not in temp:
                return False
            temp = temp[one]
        return True

alt