两个字符串的删除操作
动态规划
和1143相同，只要求出两个字符串的最长公共子序列长度即可，那么除了最长公共子序列之外的字符都是必须删除的，最后用两个字符串的总长度减去两个最长公共子序列的长度就是删除的最少步数。
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=0 ;i<word1.size() ;i++) { for(int j=0 ;j<word2.size() ;j++) { if(word1[i] == word2[j]) dp[i+1][j+1] = dp[i][j] + 1; else dp[i+1][j+1] = max(dp[i][j+1],dp[i+1][j]); } } return word1.size() + word2.size() - 2*dp[word1.size()][word2.size()]; } };
二刷
class Solution { public: int minDistance(string word1, string word2) { vector<vector<int>> dp(word1.size()+1 , vector<int>(word2.size()+1 ,0)); for(int j=0 ; j<=word2.size() ;j++) dp[0][j] = j; for(int i=0 ; i<= word1.size() ;i++) dp[i][0] = 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] = min(dp[i-1][j-1] , dp[i-1][j]+1); else dp[i][j] = min(dp[i-1][j]+1 ,dp[i][j-1]+1); } } return dp[word1.size()][word2.size()]; } };
