leetcode 583 两个字符串的删除操作

两个字符串的删除操作

动态规划

和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()];
    }
};

这篇好文章是转载于：学新通技术网