代码之家 › 专栏 › 技术社区 › peoro

“相邻”串的构建图

graph language-agnostic string algorithm

peoro · 技术社区 · 14 年前

我有一组字符串,需要建立一个图,其中字符串是节点,并且在任意一对相邻串。

到字符串 A 和 B 据说是相邻如果通过添加、删除或替换 一 (在任何位置)你得到 乙 .

例如 scar 和 car 相邻(移除 s 从 疤痕 )也是。 汽车 和 far (更换 c 具有 f )而且也是如此 远的 和 farm (添加 m )

在不到 O(n^2) ?

2 回复 | 直到 14 年前

jason 14 年前

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

(注意 n 我可以找到一个字母表和一组单词 n 单词是邻接的,图表是完整的。)

Dr. belisarius 14 年前

我认为这是不可能的。

在最坏的情况下,所有的词都是邻居。示例6 words=cat,fat,rat,mat,sat,at。

在本例中,需要建立(n)*(n-1)/2=6*5/2=15个边。

所以你需要O(n^2)操作来设置最坏情况下的边缘…不管你需要多少个比较或者循环,你都不能更好。

推荐文章

Rosie Lomas · 在ggplot中设置数字刻度

2 年前

Mahin Rahman · 我的培训和测试图表保持不变,有人能帮我解释一下,或者解释一下我哪里出错了?

3 年前

nedlaback · 在O(V+E)图中寻找瓶颈边

7 年前

Skampak · R visNetwork:创建新类型的边

7 年前

Habil Ganbarli · 在完整图上进行MST聚类(用于余弦相似性)

7 年前

Vaibhav · 在r Shinny中的Visnetwork中撤消单击事件

7 年前

Anuja · 长度l在R中的最短路径

7 年前

Cbhihe · 优化Neo4j查询,有条件地创建新关系

7 年前

fghjk · 绘制轨迹(python)

7 年前

LBerger · 计算图形图像中的名称使用(TensorBoard)

7 年前