72. Edit Distance
题目
要想把字符串S1变成S2，可以经过若干次下列原子操作：
1.删除一个字符
2.增加一个字符
3.更改一个字符
字符串S1和S2的编辑距离定义为从S1变成S2所需要原子操作的最少次数。
解法跟上面的最长公共子序列十分相似，都是动态规划，把一个问题转换为若干个规模更小的子问题，并且都借助于一个二维矩阵来实现计算。
约定：字符串S去掉最后一个字符T后为S'，T1和T2分别是S1和S2的最后一个字符。
则dist(S1,S2)是下列4个值的最小者：
1.dist(S1',S2')--当T1==T2
2.1+dist(S1',S2)--当T1!=T2，并且删除S1的最后一个字符T1
3.1+dist(S1,S2')--当T1!=T2，并且在S1后面增加一个字符T2
4.1+dist(S1',S2')--当T1!=T2，并且把S1的最的一个字符T1改成T2
解析
// 72. Edit Distance
class Solution_72 {
public:
//把问题转换为二维矩阵：
// arr[i][j]表示S1.sub(0, i)和S2.sub(0, j)的编辑距离，则
// arr[i][j] = min{ 1 + arr[i][j - 1], 1 + arr[i - 1][j], 1 + arr[i - 1][j - 1](当S1[i] != S2[j]), arr[i - 1][j - 1](当S1[i] == S2[j]) }
//边界情况：arr[0][j] = j, arr[i][0] = i
int minDistance(string word1, string word2) {
if (word1.empty()&&word2.empty())
{
return 0;
}
int n = word1.size();
int m = word2.size();
vector<vector<int>> dp(n + 1, vector<int>(m+1, 0));
for (int i = 0; i <= n; i++)
{
dp[i][0] = i;
}
for (int j = 0; j <= m;j++)
{
dp[0][j] = j;
}
for (int i = 1; i <= n;i++)
{
for (int j = 1; j <= m;j++)
{
//S!-->S2; 当前匹配字符T1==T2,dp[i-1][j-1];不匹配时，删除T1,1+dp[i-1][j];增加T1,那么T1与j匹配，剩下i和j-1匹配,1+dp[i][j-1];更改T1,1+dp[i-1][j-1]
if (word1[i-1]==word2[j-1])
{
dp[i][j] = dp[i - 1][j - 1];
}
else
{
dp[i][j] =min(1 + dp[i - 1][j - 1], min(1 + dp[i - 1][j], 1 + dp[i][j - 1]));
}
}
}
return dp[n][m];
}
};
题目来源