AcWing 902. 最短编辑距离
原题链接
简单
作者:
GinSoda
,
2019-10-08 00:54:30
,
所有人可见
,
阅读 1106
/*
思路:该题目是本质是一个图论
例子: horse <-(替换)-> rorse <-(删除|添加)-> rose <-(删除|添加)-> ros
求的是从horse到ros最短的距离。由于边上的操作是对称的,所以该图是一个无向图,最小编辑距离具有对称性。
求a到b的最小编辑距离也就等价于求b到a的最小编辑距离
对一个单词三种操作,就代表对a、b的六种操作
替换a的字符 <=> 替换b的字符
向a添加字符 <=> 删除b的字符
删除a的字符 <=> 向b添加字符
状态表示:
dp[i][j]代表a[:i+1]到b[:j+1]的最小编辑距离
状态划分:(对应6种操作)
1、替换a[i]或者b[j]:
dp[i][j] = dp[i-1][j-1] + (1 or 0)
2、插入a[i]:
dp[i-1][j] -(插入a[i])-> dp[i][j]
dp[i-1][j] = dp[i][j] + 1 (通过第i+1行求第i行,不符合动态规划)
3、删除a[i]:
dp[i][j] -(删除a[i])-> dp[i-1][j]
dp[i][j] = dp[i-1][j] + 1
4、插入b[i]:
dp[i][j-1] -(插入b[i])-> dp[i][j]
dp[i][j-1] = dp[i][j] + 1 (通过同一行第i+1列求第i列,不符合动态规划)
5、删除b[j]:
dp[i][j] -(删除b[j])-> dp[i][j-1]
dp[i][j] = dp[i][j-1] + 1
2、4不能动态规划,选取1、3、5操作
递归公式:
dp[i][j] = min(dp[i-1][j] + 1, dp[i][j-1] + 1, dp[i-1][j-1] + 1/0)
初始化:
dp[0][0]代表空字符串和空字符串
dp[i][0] = i
dp[0][j] = j
*/
class Solution {
public:
int minDistance(string word1, string word2) {
word1 = " " + word1, word2 = " " + word2; // f[0][0]代表空字符串和空字符串
int m = word1.size(), n = word2.size();
vector<vector<int>> f(m, vector<int>(n, 0));
//初始化
for(int i=0; i < m; i++) f[i][0] = i;
for(int j=0; j < n; j++) f[0][j] = j;
//递归公式
int rep = 0;
for(int i = 1; i < m; i++ ) {
for (int j = 1; j < n; j++) {
if (word1[i] == word2[j]) rep = -1;
else rep = 0;
f[i][j] = 1 + min(f[i-1][j-1]+rep, min(f[i][j-1], f[i-1][j]));
}
}
return f[m-1][n-1];
}
};