關於編輯距離的困惑

Question

使用編輯距離我必須找到兩個字符串之間有多少編輯，我已經在下面的代碼中完成了這些編輯，但是im卡住的部分正在打印輸出假設要查看的2d數組像這樣：

int editdistance(char *s, int ls, char *t, int lt) 
{ 
    int a, b, c; 
    if (!ls) return lt; 

    if (!lt) return ls; 

    if (s[ls] == t[ls]) 
      return editdistance(s, ls - 1, t, lt - 1); 
    a = editdistance(s, ls - 1, t, lt - 1); 
    b = editdistance(s, ls,  t, lt - 1); 
    c = editdistance(s, ls - 1, t, lt ); 

    if (a > b) a = b; 
    if (a > c) a = c; 

    return a + 1; 
} 

int main() 
{ 
char s1[100]; 
char s2[100]; 
printf("first: \n"); 
scanf("%s",s1); 
printf("second: \n"); 
scanf("%s",s2); 

printf("edit distance: %d\n", editdistance(s1, strlen(s1), s2, strlen(s2))); 

    return 0; 
} 

Answer 1

如果我是正確的，你正在尋找Levenshtein distance。這是Dynamic programming中的算法。