递归实现
int edit_distance(char *a, char *b, int i, int j)
{
if (j == 0) {
return i;
} else if (i == 0) {
return j;
// 算法中 a, b 字符串下标从 1 开始,c 语言从 0 开始,所以 -1
} else if (a[i-1] == b[j-1]) {
return edit_distance(a, b, i - 1, j - 1);
} else {
return min_of_three(edit_distance(a, b, i - 1, j) + 1,
edit_distance(a, b, i, j - 1) + 1,
edit_distance(a, b, i - 1, j - 1) + 1);
}
}
edit_distance(stra, strb, strlen(stra), strlen(strb));
使用递归性能低下,有很多子问题已经求解过,所以使用动态规划
动态规划实现
int edit_distance(char *a, char *b)
{
int lena = strlen(a);
int lenb = strlen(b);
int d[lena+1][lenb+1];
int i, j;
for (i = 0; i <= lena; i++) {
d[i][0] = i;
}
for (j = 0; j <= lenb; j++) {
d[0][j] = j;
}
for (i = 1; i <= lena; i++) {
for (j = 1; j <= lenb; j++) {
// 算法中 a, b 字符串下标从 1 开始,c 语言从 0 开始,所以 -1
if (a[i-1] == b[j-1]) {
d[i][j] = d[i-1][j-1];
} else {
d[i][j] = min_of_three(d[i-1][j]+1, d[i][j-1]+1, d[i-1][j-1]+1);
}
}
}
return d[lena][lenb];
}
使用之前使用pip
安装Levenshtein
pip install python-Levenshtein
import Levenshtein
string_1 = "jerry"
string_2 = "jary"
Levenshtein.distance(','.join(string_1), ','.join(string_2))