1

我正在在线进行代码挑战，涉及找到通过 Levenshtein 距离相关的单词的“社交网络”。我的 Levenshtein 函数是正确的。我递归地添加到一个全局集，并且我使用元组映射到布尔值来缓存任何一对单词的 Levenshtein 距离是否为 1。代码应该在5 秒内终止。 我不确定这怎么可能。我确信有一些aha洞察力使这成为可能。任何人都可以立即看到这一点吗？

问题陈述： 如果两个单词的 Levenshtein 距离为 1，则它们是朋友。也就是说，您可以添加、删除或替换单词 X 中的一个字母来创建单词 Y。一个单词的社交网络由它的所有朋友组成，加上他们所有的朋友，以及他们所有朋友的朋友，等等。使用这个单词列表编写一个程序，告诉我们“hello”这个词的社交网络有多大

我的伪代码：

get_network(friend)
  if friend not in network
    add friend to network
    friends = []
    check friend against all words in network
      consult cache or calculate lev distance
      cache if necessary, append to friends if necessary
    for all friends
      get_network(friend)

换个说法： “使效率大幅提升的基本洞察力是什么？”

4

0 回答 0