dp[i][j]表示由word1的前i个字符转换为word2的前j个字符的最小编辑距离。状态公式:
- 如果
word1[i-1] = word2[j-1]
,dp[i][j] = dp[i-1][j-1]
- 如果
word1[i-1] != word2[j-1]
,dp[i][j] = min(dp[i-1][j-1]+1, dp[i][j-1]+1, dp[i-1][j] + 1)
- 基准1:
dp[0][k] = k
- 基准2:
dp[k][0] = k
状态公式的解释如下:
- 如果word1的第i个字符和word2的第j个字符相等,那么最小编辑距离等于
dp[i-1][j-1]
的最小编辑距离 - 如果word1的第i个字符和word2的第j个字符不相等,那么最小编辑距离等于如下值中的最小者:
word1的前i-1个字符到word2的前j-1个字符所需编辑距离
+1(插入)word1的前i-1个字符到word2的前j个字符所需编辑距离
+1(删除)word1的前i个字符到word2的前j-1个字符所需编辑距离
+1(插入)
- 基准1: 如果word1为空,那么到word2的编辑距离为word2的长度(持续插入)
- 基准2: 如果word2为空,那么到word2的编辑距离为word1的长度(持续删除)
判断是否适用动态规划解法的两个直观条件——a.当前状态和前面状态相关、b.存在基准条件
代码如下:
非常重要:注意搞清楚word1[i]/word2[j]中i/j以及dp[i][j]中i/j的区别,否则循环的边界条件及表达式极容易出问题
// // Created by jt on 2020/8/30. // #include <string> #include <vector> #include <algorithm> using namespace std; class Solution { public: /** * * @param word1 string字符串 * @param word2 string字符串 * @return int整型 */ int minDistance(string word1, string word2) { // write code here vector<vector<int> > dp(word1.size() + 1, vector<int>(word2.size() + 1, 0)); for (int i = 1; i <= word1.size(); ++i) dp[i][0] = i; for (int i = 1; i <= word2.size(); ++i) dp[0][i] = i; for (int i = 1; i <= word1.size(); ++i) { for (int j = 1; j <= word2.size(); ++j) { if (word1[i-1] == word2[j-1]) dp[i][j] = dp[i-1][j-1]; else dp[i][j] = min(dp[i-1][j-1], min(dp[i-1][j], dp[i][j-1])) + 1; } } return dp[word1.size()][word2.size()]; } };