编辑距离

 1 /***************************************
 2 FileName EditDistance.cpp
 3 Author : godfrey
 4 CreatedTime : 2016/5/1
 5 ****************************************/
 6 #include <iostream>
 7 #include <cstring>
 8 #include <stdio.h>
 9 #include <stdlib.h>
10 
11 using namespace std;
12 //两个字符串经过增删改操作，用最少的次数使两个字符串相同
13 int32_t EditDistance(char* str1,char* str2){
14     int32_t len1 = strlen(str1);
15     int32_t len2 = strlen(str2);
16     int32_t h[len1+1][len2+1];
17     int32_t MinNum;
18     for(int i=0;i<=len1;i++)
19         h[i][0] = i;
20     for(int j=0;j<=len2;j++)
21         h[0][j] = j;
22     for(int i=1;i<=len1;i++){
23         for(int j=1;j<=len2;j++){
24             MinNum = len1 + len2;
25             if(str1[i-1] == str2[j-1] && MinNum > h[i-1][j-1])
26                 MinNum = h[i-1][j-1];
27             if(str1[i-1] != str2[j-1]){
28                 if(MinNum > h[i-1][j] + 1){
29                     MinNum = h[i-1][j] + 1;
30                 }
31                 if(MinNum > h[i][j-1] + 1){
32                     MinNum = h[i][j-1] + 1;
33                 }
34                 if(MinNum > h[i-1][j-1]+1){
35                     MinNum = h[i-1][j-1] + 1;
36                 }
37             }
38             h[i][j] = MinNum;
39         }
40     }
41     return h[len1][len2];
42 }
43 int main()
44 {
45     char str1[1024],str2[1024];
46     int32_t num;
47     while(scanf("%s%s",str1,str2)!=EOF){
48         num = EditDistance(str1,str2);
49         printf("EditDistance: %d\n",num);
50     }
51     return 0;
52 }