|
vivaxy's Blog |
博客
简介 Levenshtein 距离是一种编辑距离，用来表示两个字符串的差异。编辑距离是指从字符串 A 开始，修改成字符串 B 的最小步骤数，每个以步骤中，你可以删除一个字符、修改一个字符或者新增一个字符。 比如我们把 acat 变成 gate 的时候，需要做如下的修改： 删除 a 把 c 改成 g 新增 e 所以 acat 和 gate 的 Levenshtein 距离是 3。 算法 这里使用动态规划的方式来实现。 记 Levenshtein 距离为 l(i, j)，i 是字符串 A 中从开头到第 i 个下标的子字符串，j 是字符串 B 从开头到第 j 个下标的子字符串，i 和 j 都从 0 开始。...