0

这是一个取自这里的问题

如果两个词的 Levenshtein 距离为 1，则它们是朋友（有关详细信息，请参阅http://en.wikipedia.org/wiki/Levenshtein_distance）。也就是说，您可以添加、删除或替换单词 X 中的一个字母来创建单词 Y。一个单词的社交网络包括它的所有朋友，加上他们的所有朋友，以及他们所有朋友的朋友，等等. 编写一个程序，告诉我们“hello”这个词的社交网络有多大，使用这个词列表https://raw.github.com/codeeval/Levenshtein-Distance-Challenge/master/input_levenshtein_distance.txt 输入

你的程序应该接受一个文件名的路径作为它的第一个参数。输入文件包含单词列表。此列表也可在https://raw.github.com/codeeval/Levenshtein-Distance-Challenge/master/input_levenshtein_distance.txt 获得

打印出“你好”这个词的社交网络有多大。例如，单词“abcde”的社交网络是 4846。

任何人都可以帮助提出一些相同的逻辑。这不是家庭作业问题。

4

3 回答 3

5

一个简单的O(n^2)解决方案是将问题建模为图形：
G = (V,E)、位置V = { all words }和E = { (u,v) | u is friend of v }。

由此，下一个算法如下（高级伪代码）：

1. Create the graph from the data
2. Run a BFS from the source, and continue while there are more 
   vertices that can be discovered. 
3. When you are done, the size of the `visited` set is the size of 
   the social network (this set is the actual social network)

复杂：

  • 创建此图是O(n^2)（检查所有对）。
  • BFS也是O(n^2)因为|E| < n^2，所以你得到了O(n^2)算法的总数。
于 2012-05-25T11:31:03.753 回答
2

您可以使用 BFS 或 DFS 或任何返回图树覆盖的算法，这非常符合您的口味。

于 2012-05-25T13:22:39.477 回答
2

如果您知道如何找到 Levenshtein 距离，那么您只需要知道这对单词之间的 Levenstein 距离。

在这里您不需要绘制完整的图表。更好的方法是维护一个你知道在单词的社交网络中的单词的哈希表。这样，您将避免冗余对。这正是我的意思。

假设单词是：Right Bright Wright

所有对的编辑距离均为 1。但是，如果您只想要 Right 的社交网络，则无需考虑 Bright 和 Wright 这对搭档。

以这种方式继续检查所有检查的单词，直到检查列表中没有添加。

于 2012-05-25T14:13:21.027 回答