字典树实现拼音九键按照词典的词频进行提示补全算法
class Trieroot():
def __init__(self):
self.isEnd = False
self.next = {}
self.pre = ""
self.count = 0
class Trie(object):
def __init__(self):
self.root = Trieroot()
self.w2i_dict = {}
self.w2i_dict['a'] = 2
self.w2i_dict['b'] = 2
self.w2i_dict['c'] = 2
self.w2i_dict['d'] = 3
self.w2i_dict['e'] = 3
self.w2i_dict['f'] = 3
self.w2i_dict['g'] = 4
self.w2i_dict['h'] = 4
self.w2i_dict['i'] = 4
self.w2i_dict['j'] = 5
self.w2i_dict['k'] = 5
self.w2i_dict['l'] = 5
self.w2i_dict['m'] = 6
self.w2i_dict['n'] = 6
self.w2i_dict['o'] = 6
self.w2i_dict['p'] = 7
self.w2i_dict['q'] = 7
self.w2i_dict['r'] = 7
self.w2i_dict['s'] = 7
self.w2i_dict['t'] = 8
self.w2i_dict['u'] = 8
self.w2i_dict['v'] = 8
self.w2i_dict['w'] = 9
self.w2i_dict['x'] = 9
self.w2i_dict['y'] = 9
self.w2i_dict['z'] = 9
def insert(self,word):
node = self.root
for st in word:
ind = self.w2i_dict[st]
if ind not in node.next:
node.next[ind] = Trieroot()
node = node.next[ind]
node.isEnd = True
node.pre = word
node.count+=1
def startwith(self,inter):
def show(node):
if node.isEnd:
save[node.pre] = node.count
for ind in node.next:
show(node.next[ind])
node = self.root
for ind in inter:
ind = int(ind)
if ind not in node.next:
return False
node = node.next[ind]
#print(node.pre)
save = {}
show(node)
#print(save)
print(sorted(save,reverse=True))
算法分析 空间复杂度O(26N) 其中N为最长的单词长度
时间复杂度插入O(N);前缀O(26(N-M)) 其中N为输入长度M为字典中最长单词的长度
