Python -用递归函数按字母顺序打印trie
Python -用递归函数按字母顺序打印trie
提问于 2019-11-01 01:28:01
我正努力通过伯德，克莱因和洛珀的NLTK书，我和我被困在一个问题。我在翻阅这本书，是为了个人的充实，而不是为了一堂课。
我遇到的问题是4.29：
编写了一个递归函数，它按字母顺序打印trie，例如：
chair: 'flesh' ---t: 'cat' --ic: 'stylish' ---en: 'dog'
我正在使用这本书中的代码来创建trie：
def insert(trie, key, value):
if key:
first, rest = key[0], key[1:]
if first not in trie:
trie[first] = {}
insert(trie[first], rest, value)
else:
trie['value'] = value
trie = {}
insert(trie, 'chat', 'cat')
insert(trie, 'chien', 'dog')
insert(trie, 'chair', 'flesh')
insert(trie, 'chic', 'stylish')我从这一讨论修改了一个函数的答案，该函数递归地遍历trie并提取完整的键和值：
def trawl_trie(trie):
unsorted = []
for key, value in trie.items():
if 'value' not in key:
for item in trawl_trie(trie[key]):
unsorted.append(key + item)
else:
unsorted.append(': ' + value)
return unsorted但是，我不能使用递归来创建一个字母列表，我也不知道如何使用递归来替换键的重复部分。我所能做的最好的就是创建一个助手函数，它将遍历上述函数的结果：
def print_trie(trie):
# sort list alphabetically
alphabetized = list(sorted(set(trawl_trie(trie))))
print(alphabetized[0])
# compare the 2nd item ~ to the previous one in the list.
for k in range(1, len(alphabetized)):
# separate words from value
prev_w, prev_d = (re.findall(r'(\w+):', alphabetized[k - 1]), re.findall(r': (\w+)', alphabetized[k - 1]))
curr_w, curr_d = (re.findall(r'(\w+):', alphabetized[k]), re.findall(r': (\w+)', alphabetized[k]))
word = ''
# find parts that match and replace them with dashes
for i in range(min(len(prev_w[0]), len(curr_w[0]))):
if prev_w[0][i] == curr_w[0][i]:
word += prev_w[0][i]
curr_w[0] = re.sub(word, '-' * len(word), curr_w[0])
print(curr_w[0] + ": " + str(curr_d[0]))这将是产出：
print_trie(trie)
chair: flesh
---t: cat
--ic: stylish
---en: dog有人知道用一个递归函数是否有可能得到相同的结果吗？或者我被困在使用递归函数来遍历trie，而使用第二个助手函数来使一切看起来很好？
干杯,
- MC
回答 2
Stack Overflow用户
回答已采纳
发布于 2019-11-01 02:48:50
def insert(trie, key, value):
"""Insert into Trie"""
if key:
first, rest = key[0], key[1:]
if first not in trie:
trie[first] = {}
insert(trie[first], rest, value)
else:
trie['value'] = value
def display(trie, s = ""):
"""Recursive function to Display Trie entries in alphabetical order"""
first = True
for k, v in sorted(trie.items(), key = lambda x: x[0]):
# dictionary sorted based upon the keys
if isinstance(v, dict):
if first:
prefix = s + k # first to show common prefix
first = False
else:
prefix = '-'*len(s) + k # dashes for common prefix
display(v, prefix) # s+k is extending string s for display by appending current key k
else:
print(s, ":", v) # not a dictionary, so print current # not a dictionary, so print current string s and value
# Create Trie
trie = {}
insert(trie, 'chat', 'cat')
insert(trie, 'chien', 'dog')
insert(trie, 'chair', 'flesh')
insert(trie, 'chic', 'stylish')
#Display Use Recursive function (second argument will default to "" on call)
display(trie)输出
chair : flesh
---t : cat
--ic : stylish
---en : dogStack Overflow用户
发布于 2019-11-01 05:52:28
我修改了DarrylG的答案(，再次感谢！)，添加了通过递归传递的可接受键列表，以及迭代此列表的一对for-loops，以查看字符串开头是否有可替换的公共元素。
编辑11/2/19:这个修改有一个我没有注意到的错误。它将第一次正确运行，但在后续运行时，它将替换过多的字符，即：。
----r: flesh
---t: cat
---c: stylish
----n: dogdef insert(trie, key, value):
"""Insert into Trie"""
if key:
first, rest = key[0], key[1:]
if first not in trie:
trie[first] = {}
insert(trie[first], rest, value)
else:
trie['value'] = value
def display(trie, s = "", final = []):
"""Recursive function to Display Trie entries in alphabetical order"""
for k, v in sorted(trie.items(), key = lambda x: x[0]):
# dictionary sorted based upon the keys
if isinstance(v, dict):
display(v, s + k, final) # s+k is extending string s for display by appending current key k
else:
# replace common elements at beginning of strings with dashes
i = sum([any([f.startswith(string[:j]) for f in final]) for j in range(1, len(string))])
string = '-' * i + s[i:]
print(string + ":", v) # not a dictionary, so print current edited s and value
final.append(s)
# Create Trie
trie = {}
insert(trie, 'chat', 'cat')
insert(trie, 'chien', 'dog')
insert(trie, 'chair', 'flesh')
insert(trie, 'chic', 'stylish')
#Display Use Recursive function (second argument will default to "" on call)
display(trie)页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/58653062
复制相关文章
相似问题
腾讯云开发者
Copyright © 2013 - 2026 Tencent Cloud. All Rights Reserved. 腾讯云 版权所有
深圳市腾讯计算机系统有限公司 ICP备案/许可证号：粤B2-20090059 
粤公网安备44030502008569号
腾讯云计算（北京）有限责任公司 京ICP证150476号 | 京ICP备11018762号