forked from ztianming/xuexi.cn
-
Notifications
You must be signed in to change notification settings - Fork 0
/
Trie.py
71 lines (65 loc) · 2.08 KB
/
Trie.py
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
62
63
64
65
66
67
68
69
70
71
# -*- coding: UTF-8 -*-
import queue
class TrieNode:
def __init__(self):
self.end = [] # 以此结束的题目序号列表
self.char = "" # 自己代表的字符
self.pointers = [] # 指向的节点
self.pointerLabels = [] # 指向的字符标签
rootNode = TrieNode()
# 根据字符串数据构建Trie树
def createTrie(strlist):
for str in strlist:
cur = rootNode
for i in range(str):
ch = str[i]
if ch not in cur.pointerLabels:
# 添加新节点
cur.pointerLabels.append(ch)
newNode = TrieNode()
newNode.char = ch
cur.pointers.append(newNode)
# if i != len(str)-1:
cur = newNode
else: # 说明在下面找到了
pos = cur.pointerLabels.index(ch)
cur = cur.pointers[pos]
cur.end.append(-1) # 添加序号
def addTrieOne(num, str):
cur = rootNode
for i in range(len(str)):
ch = str[i]
if ch not in cur.pointerLabels:
# 添加新节点
cur.pointerLabels.append(ch)
newNode = TrieNode()
newNode.char = ch
cur.pointers.append(newNode)
# if i != len(str)-1:
cur = newNode
else: # 说明在下面找到了
pos = cur.pointerLabels.index(ch)
cur = cur.pointers[pos]
cur.end.append(num) # 添加题目序号
def findQuesByTrie(x):
cur = rootNode
for i in range(len(x)):
ch = x[i]
if ch not in cur.pointerLabels:
return []
else:
pos = cur.pointerLabels.index(ch)
cur = cur.pointers[pos]
# 找到cur之后往下面遍历一下把所有对应的序号都输出一下就可以了
res = []
nodeQue = queue.Queue()
nodeQue.put(cur)
while nodeQue.qsize() != 0:
topnode = nodeQue.get()
for i in topnode.end:
res.append(i)
for i in topnode.pointers:
nodeQue.put(i)
return res
if __name__ == "__main__":
pass