我有一组字符串,需要构建一个图,其中字符串是节点,任何一对相邻字符串之间都有边。
对于字符串 A
和 B
如果通过添加、删除或替换 A 的单个字符,则称其为 adjacent
(在任何位置)你得到 B
。
例如 scar
和 car
相邻(从 scar
中删除 s
),car
和 far
(将 c
替换为 f
)等 far
和 农场
(添加m
)。
是否可以在 O(n^2)
内完成此操作?
最佳答案
您必须计算邻接矩阵中的 n(n - 1)/2 = O(n^2)
个条目(如果 Levenshtein distance 为 1,则条目为 1,否则为 0 ).这是无法避免的。
(请注意,给定 n
,我可以找到一个字母表和该字母表上的一组单词,这样所有 n
单词都是相邻的,并且该图将是完整的。 )
关于algorithm - "adjacent"字符串的构建图,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/4195963/