2023.8.26
本题看似很绕,其实就是 最长公共子序列 的变式。 求出最长公共子序列之后,再用两单词的总长度减去他们的最长公共子序列即可。
代码如下:
class Solution {
public:int minDistance(string word1, string word2) {vector<vector<int>> dp(word1.size()+1,vector<int>(word2.size()+1,0));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] + 1;else dp[i][j] = max(dp[i-1][j],dp[i][j-1]);}}return word1.size()+word2.size()-2*dp[word1.size()][word2.size()];}
};
附上草稿图以供参考: