C++ DP with Explanation


  • 0
    Z

    The allowed operation is "Delete" only, but actually the "Delete" operation on both strings is equal to "Delete" and "Add" on just one string. Then the problem becomes straightforward, given a src string word1 and target string word2, and the allowed operations are "Delete" or "Add" a letter on the source string, we just need to find the minimum operations to convert to the target string.

    class Solution {
    public:
        int minDistance(string word1, string word2) {
            if (word1.empty()) return word2.length();
            if (word2.empty()) return word1.length();
            int len1 = word1.length(), len2 = word2.length();
            vector<vector<int>> dp(len1 + 1, vector<int>(len2 + 1, 0));
            for (int i = 1; i <= len1; i++) dp[i][0] = i;
            for (int j = 1; j <= len2; j++) dp[0][j] = j; 
            for (int i = 1; i <= len1; ++i) {
                for (int j = 1; j <= len2; ++j) {
                    if (word1[i - 1] == word2[j - 1]) dp[i][j] = dp[i - 1][j - 1];
                    else dp[i][j] = 1 + min(dp[i - 1][j], dp[i][j - 1]);
                }
            }
            return dp[len1][len2];
        }
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.