如何分组相隔一个编辑距离的字符串

Question

我有一个字符串列表，比如：

arr1 = ["ABC", "ABD", "ABCD", "ABCE", "ACCE", "AB"]

我想把这些字符串分成几个小组，每个小组里的字符串之间的差别是x-edit-distance。简单来说，x-edit-distance就是指通过替换某个字母来让两个字符串变得相似。例如，如果是1-edit-distance，那就是只需要把一个字母换成别的字母就可以了。所以对于上面的列表，我想得到：

arr2 = [["ABC", "ABD"], ["ABCD", "ABCE", "ACCE"], ["AB"]]

有没有什么算法可以解决这个问题？有没有什么有效的方法来处理这个？

补充一下，我所说的edit-distance有点不同：我只允许替换x个字母（如果x=1，那就只能有1个字母不同），不允许添加或删除字母。

Answer 1

你可以把每个字符串当作图中的一个点（我们叫它“顶点”）。如果两个字符串之间的编辑距离是x，那么这两个点之间就可以连一条线（我们叫它“边”）。接下来，你只需要运行一个深度优先搜索（DFS）来找到你需要的分组。

如果你需要更多细节，随时告诉我。

Answer 2

你给出的例子里的算法，可能并不是你真正想要的那种算法，但这也是有可能的：

editdist = lambda a, b: sum(0 if c1 == c2 else 1 for (c1, c2) in zip(a, b))
a = ["ABC", "ABD", "ABCD", "ABCE", "ACCE", "AB"]
a = list(reversed(a))
ret = []
while a:
    s = a.pop()
    for sublist in ret:
        if len(sublist[-1]) == len(s) and editdist(sublist[-1], s) == 1:
            sublist.append(s)
            s = None
            break
    if s: ret.append([s])
print ret

这段代码假设你想要的结果是：一系列字符串，这些字符串之间的关系是，每个字符串和前一个字符串、后一个字符串的差别只有一个字符的距离。