algorithm - "adjacent"字符串的构建图

Question

我有一组字符串，需要构建一个图，其中字符串是节点，任何一对相邻字符串之间都有边。

对于字符串 A 和 B 如果通过添加、删除或替换 A 的单个字符，则称其为 adjacent (在任何位置)你得到 B。

例如 scar 和 car 相邻(从 scar 中删除 s)，car 和 far(将 c 替换为 f)等 far 和 农场(添加m)。

是否可以在 O(n^2) 内完成此操作？

Answer 1

您必须计算邻接矩阵中的 n(n - 1)/2 = O(n^2) 个条目(如果 Levenshtein distance 为 1，则条目为 1，否则为 0 ).这是无法避免的。

(请注意，给定 n，我可以找到一个字母表和该字母表上的一组单词，这样所有 n 单词都是相邻的，并且该图将是完整的。 )