Question

这是从"这里提取的问题。

Two words are friends if they have a Levenshtein distance of 1 (For details see http://en.wikipedia.org/wiki/Levenshtein_distance). That is, you can add, remove, or substitute exactly one letter in word X to create word Y. A word’s social network consists of all of its friends, plus all of their friends, and all of their friends’ friends, and so on. Write a program to tell us how big the social network for the word hello is, using this word list https://raw.github.com/codeeval/Levenshtein-Distance-Challenge/master/input_levenshtein_distance.txt Input

Your program should accept as its first argument a path to a filename.The input file contains the word list. This list is also available at https://raw.github.com/codeeval/Levenshtein-Distance-Challenge/master/input_levenshtein_distance.txt Output

例如,abcde一词的社会网络是4846。

Can any one help to come up with some logic for the same. It is not a home work problem.

Answer 1

A simple O(n^2) solution would be to model the problem as a graph:
G = (V,E), where V = { all words } and 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)

<强度 > 复杂度:

Creating this graph is O(n^2) (check all pairs).
BFS is also O(n^2) since |E| < n^2, so you get total of O(n^2) algorithm.

Answer 2

如果你知道如何找到Levenshtein距离, 你需要知道的只是两个词之间的Levenstein距离。

在这里您不需要绘制完整的图表。更好的方法将是维持一个散列表格, 上面写着您知道的单词。这样您就可以避免多余的对子。这正是我的意思。

Suppose the words are: Right Bright Wright

所有对子都有一个编辑距离。但如果你只想要 Rights S 社交网络, 你不需要考虑对对Bright和Wright。

继续这样对所检查的所有单词进行检查, 直到您所检查的列表中没有添加。

Answer 3

您可以使用 BFS 或 DFS 或任何算法来返回图形的树覆盖, 它与您的口味相当相近。

友情链接