使用Levenshtien距离的社交网络

Question

这是取自一个问题在这里

如果Levenshtein距离为1,则两个单词是朋友(有关详细信息,请参阅http://en.wikipedia.org/wiki/Levenshtein_distance).也就是说,您可以在单词X中添加,删除或替换正好一个字母来创建单词Y.单词的社交网络由其所有朋友,所有朋友以及他们所有朋友的朋友组成,依此类推.写一个程序,告诉我们"你好"这个词的社交网络有多大,使用这个单词列表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.

任何人都可以帮助提出相同的逻辑.这不是家庭工作的问题.

Answer 1

一个简单的O(n^2)解决方案是将问题建模为图形:
G = (V,E),where 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)算法.