【转】字符串编辑距离

原文：http://m.blog.csdn.net/blog/cqs_2012/17849877

题目

有两个字符串A和B，对A可以进行如下的操作：插入一个字符，删除一个字符，替换一个字符。问A可以通过最少多少次操作变为B？我们定义这个结果为字符串的最小编辑距离。

思路（借鉴九章算法的，感觉挺好，所以实现，共同学习）

字符串编辑距离归为DP题目，所以还是超好的

 1 for(int i = 0;i<int(b.size()+1);i++)
 2         dp[i] = new int[a.size()+1]; 
 3     for(int i = 0; i<int(a.size()+1);i++)
 4         dp[0][i] = i;
 5     for(int i = 1; i<int(b.size()+1);i++)
 6         dp[i][0] = i;
 7     for(int i = 1; i<int(b.size()+1);i++)
 8         for(int j=1; j<int(a.size()+1);j++)
 9             if( a[j-1] != b[i-1] )
10                 dp[i][j] = min (dp[i-1][j],dp[i][j-1],dp[i-1][j-1])+1;
11             else 
12                 dp[i][j] = min (dp[i-1][j]+1,dp[i][j-1]+1,dp[i-1][j-1]);
13     return dp[b.size()][a.size()];

实验

代码

 1 #include<iostream>
 2 #include<string>
 3 using namespace std;
 4 
 5 // get the minest number of three numbers
 6 int min(int a,int b,int c);
 7 
 8 // get the minest distance of string a and b
 9 int zifuchuan_bianji_juli(string a,string b);
10 
11 
12 int main()
13 {
14     string a,b;
15     cout<<"please input string a and b"<<endl;
16     cin>>a>>b;
17     cout<<"a=""<<a<<"",b=""<<b<<"""<<endl;
18     cout<<"字符串距离为： "<<zifuchuan_bianji_juli(a,b)<<endl;
19     system("pause");
20     return 0;
21 }
22 
23 int zifuchuan_bianji_juli(string a,string b)
24 {
25     if( a.empty() )
26         return int( b.size() );
27     else if( b.empty())
28         return int( a.size() ) ;
29 
30     int ** dp = new int*[ b.size()+1 ];
31     for(int i = 0;i<int(b.size()+1);i++)
32         dp[i] = new int[a.size()+1]; 
33     for(int i = 0; i<int(a.size()+1);i++)
34         dp[0][i] = i;
35     for(int i = 1; i<int(b.size()+1);i++)
36         dp[i][0] = i;
37     for(int i = 1; i<int(b.size()+1);i++)
38         for(int j=1; j<int(a.size()+1);j++)
39             if( a[j-1] != b[i-1] )
40                 dp[i][j] = min (dp[i-1][j],dp[i][j-1],dp[i-1][j-1])+1;
41             else 
42                 dp[i][j] = min (dp[i-1][j]+1,dp[i][j-1]+1,dp[i-1][j-1]);
43     return dp[b.size()][a.size()];
44 }
45 
46 int min(int a,int b,int c)
47 {
48     if(a>b)
49     {
50         if(b>c)
51             return c;
52         else return b;
53     }else if(a>c)
54         return c;
55     else return a;
56 }