peo*_*oro 2 language-agnostic string algorithm graph
我有一组字符串,需要构建一个图表,其中字符串是节点,并且任何一对相邻字符串之间都有一条边.
对于字符串而言A,如果通过添加,删除或替换(在任何位置)获得的单个字符,B则称其为相邻字符串. AB
例如scar和car相邻(去除s从scar),因此是car和far(取代c与f)等都是far和farm(添加m).
是不是可以做到这一点O(n^2)？
您必须计算n(n - 1)/2 = O(n^2)邻接矩阵中的条目(如果Levenshtein距离为1 则条目为1,否则为0).没有办法避免这种情况.
(注意,给定的n,我可以在该字母表中找到一个字母和一组单词,这样所有n单词都是邻居,图表就完整了.)
我认为这是不可能的.
在最坏的情况下,所有单词都是邻居.例6 words = {cat,fat,rat,mat,sat,at}.
在此示例中,您需要建立(n)*(n-1)/ 2 = 6*5/2 = 15个边.
因此,您需要O(n ^ 2)操作才能在最坏的情况下设置边缘...无论您需要多少比较或循环,您都无法做到这一点.