Trie树，实现简易的搜索引擎的搜索关键词功能，用于具有相同前缀的字符串匹配
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
|
MAX_NUM = 26
import typing as t
class TrieNode(object):
"""
构造前缀
"""
def __init__(self, char):
self.char = char
self.children: t.Any = [None for _ in range(MAX_NUM)]
self.is_end = False
root = TrieNode('/')
def trie_insert(text: str) -> None:
"""
向trie树中插入字符串,形成一条字符串链
"""
asc_a: int = ord('a')
p: TrieNode = root
for s in text:
index: int = ord(s) - asc_a
if not p.children[index]:
child: TrieNode = TrieNode(s)
p.children[index] = child
p = p.children[index]
p.is_end = True
def trie_find(text: str) -> bool:
"""
在trie树种查找字符串
"""
asc_a: int = ord('a')
p: TrieNode = root
for s in text:
index: int = ord(s) - asc_a
if not p.children[index]:
return False
p = p.children[index]
return True if p.is_end else False
str_one = 'ilove'
str_one1 = 'ilo'
trie_insert(str_one)
trie_insert(str_one1)
str_sec = 'ilo'
res = trie_find(str_sec)
print(res)
|