字符串之字典树

发表于 | 分类于 | 阅读次数:
字数统计: 152 | 阅读时长 ≈ 1 
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


class TrieNode:
    def __init__(self, data: str):
        self._data = data
        self._children = [None] * 26
        self._is_ending_char = False
    

class Trie:
    def __init__(self):
        self._root = TrieNode("/")

    def insert(self, text: str) -> None:
        node = self._root
        for index, char in map(lambda x: (ord(x) - ord("a"), x), text):
            if not node._children[index]:
                node._children[index] = TrieNode(char)
            node = node._children[index]
        node._is_ending_char = True
    
    def find(self, pattern: str) -> bool:
        node = self._root
        for index in map(lambda x: ord(x) - ord("a"), pattern):
            if not node._children[index]: return False
            node = node._children[index]
        return node._is_ending_char


if __name__ == "__main__":

    strs = ["how", "hi", "her", "hello", "so", "see"]
    trie = Trie()
    for s in strs:
        trie.insert(s)
    
    for s in strs:
        print(trie.find(s))
    
    print(trie.find("swift"))