Minimum ASCII Delete Sum for Two Strings Solutions in C++

// Source : https://leetcode.com/problems/minimum-ascii-delete-sum-for-two-strings/
// Author : Hao Chen
// Date   : 2019-01-30



class Solution {
public:
    int minimumDeleteSum(string s1, string s2) {
        // Dynamic Programm - simlar with : Edit Distance
        vector < vector <int> > dp ( s1.size()+1, vector<int>( s2.size()+1, 0) );

        // s1 is row, s2 is column
        for (int i=1; i<=s2.size(); i++) dp[0][i] = dp[0][i-1] + s2[i-1];
        for (int i=1; i<=s1.size(); i++) dp[i][0] = dp[i-1][0] + s1[i-1];

        for (int i=1; i<=s1.size(); i++){
            for (int j=1; j<=s2.size(); j++) {
                if ( s1[i-1] == s2[j-1] ) {
                    dp[i][j] = dp[i-1][j-1];
                }else{
                    dp[i][j] = min(dp[i-1][j] + s1[i-1], dp[i][j-1] + s2[j-1]);
                }
            }
        }

        return dp[s1.size()][s2.size()];

    }
};

/// Source : https://leetcode.com/problems/minimum-ascii-delete-sum-for-two-strings/description/
/// Author : liuyubobobo
/// Time   : 2017-10-21

#include <iostream>
#include <string>

using namespace std;

/// Memory Search
/// calculate the max ASCII sum of common sequence
///
/// Time Complexity: O(len(s1) * len(s2))
/// Space Complexity:  O(len(s1) * len(s2))
class Solution {

private:
    int dp[1001][1001];

public:
    int minimumDeleteSum(string s1, string s2) {

        for(int i = 0 ; i < s1.size() ; i ++)
            for(int j = 0 ; j < s2.size() ;j ++)
                dp[i][j] = -1;

        int maxAsc = maxascLCS(s1, 0, s2, 0);

        int ascSum1 = ascSum(s1);
        int ascSum2 = ascSum(s2);

        return ascSum1 + ascSum2 - 2*maxAsc;
    }

private:
    int maxascLCS(const string& s1, int i, const string& s2, int j){

        if(i >= s1.size() || j >= s2.size())
            return 0;

        if(dp[i][j] != -1)
            return dp[i][j];

        int res = 0;
        if(s1[i] == s2[j])
            res = max(res, (int)s1[i] + maxascLCS(s1, i+1, s2, j+1));

        res = max(res, maxascLCS(s1, i+1, s2, j));
        res = max(res, maxascLCS(s1, i, s2, j+1));

        return dp[i][j] = res;
    }

    int ascSum(const string& s){

        int total = 0;
        for(int i = 0 ; i < s.size() ; i ++)
            total += (int)s[i];
        return total;
    }
};

int main() {

    cout << Solution().minimumDeleteSum("sea", "eat") << endl;
    cout << Solution().minimumDeleteSum("delete", "leet") << endl;

    return 0;
}

/// Source : https://leetcode.com/problems/minimum-ascii-delete-sum-for-two-strings/description/
/// Author : liuyubobobo
/// Time   : 2017-10-21

#include <iostream>
#include <string>

using namespace std;

/// Dynamic Programming
/// calculate the max ASCII sum of common sequence
///
/// Time Complexity: O(len(s1) * len(s2))
/// Space Complexity:  O(len(s1) * len(s2))
class Solution {

private:
    int dp[1001][1001];

public:
    int minimumDeleteSum(string s1, string s2) {

        for(int i = 0 ; i <= s1.size() ; i ++)
            dp[i][s2.size()] = 0;

        for(int j = 0 ; j <= s2.size() ; j ++)
            dp[s1.size()][j] = 0;

        for(int i = s1.size() - 1 ; i >= 0 ; i --)
            for(int j = s2.size() - 1 ; j >= 0 ; j --){
                dp[i][j] = max(dp[i+1][j], dp[i][j+1]);
                if(s1[i] == s2[j])
                    dp[i][j] = max(dp[i][j], s1[i] + dp[i+1][j+1]);
            }

        int ascSum1 = ascSum(s1);
        int ascSum2 = ascSum(s2);

        return ascSum1 + ascSum2 - 2*dp[0][0];
    }

private:
    int ascSum(const string& s){

        int total = 0;
        for(int i = 0 ; i < s.size() ; i ++)
            total += (int)s[i];
        return total;
    }
};

int main() {

    cout << Solution().minimumDeleteSum("sea", "eat") << endl;
    cout << Solution().minimumDeleteSum("delete", "leet") << endl;

    return 0;
}

/// Source : https://leetcode.com/problems/minimum-ascii-delete-sum-for-two-strings/description/
/// Author : liuyubobobo
/// Time   : 2017-10-22

#include <iostream>

using namespace std;

/// Memory Search
/// calculate the minimum delete ASCII sum for common sequence
///
/// Time Complexity: O(len(s1) * len(s2))
/// Space Complexity:  O(len(s1) * len(s2))
class Solution {

private:
    int dp[1001][1001];

public:
    int minimumDeleteSum(string s1, string s2) {

        for(int i = 0 ; i <= s1.size() ; i ++)
            for(int j = 0 ; j <= s2.size() ;j ++)
                dp[i][j] = -1;

        return minAscDelete(s1, 0, s2, 0);
    }

private:
    int minAscDelete(const string& s1, int i, const string& s2, int j){

        if(dp[i][j] != -1)
            return dp[i][j];

        if(i == s1.size() && j == s2.size())
            return dp[i][j] = 0;

        if(i == s1.size())
            return dp[i][j] = s2[j] + minAscDelete(s1, i, s2, j+1);

        if(j == s2.size())
            return dp[i][j] = s1[i] + minAscDelete(s1, i+1, s2, j);

        int res = min(s1[i] + minAscDelete(s1, i+1, s2, j),
                      s2[j] + minAscDelete(s1, i, s2, j+1));

        if(s1[i] == s2[j])
            res = min(res, minAscDelete(s1, i+1, s2, j+1));

        return dp[i][j] = res;
    }
};

int main() {

    cout << Solution().minimumDeleteSum("sea", "eat") << endl;
    cout << Solution().minimumDeleteSum("delete", "leet") << endl;

    return 0;
}

/// Source : https://leetcode.com/problems/minimum-ascii-delete-sum-for-two-strings/description/
/// Author : liuyubobobo
/// Time   : 2017-10-22

#include <iostream>
#include <vector>

using namespace std;

/// Dynamic Programming
/// calculate the minimum delete ASCII sum for common sequence
///
/// Time Complexity: O(len(s1) * len(s2))
/// Space Complexity:  O(len(s1) * len(s2))
class Solution {

public:
    int minimumDeleteSum(string s1, string s2) {

        vector<vector<int>> dp(s1.size()+1, vector<int>(s2.size()+1, 0));

        for(int i = s1.size()-1 ; i >= 0 ; i --)
            dp[i][s2.size()] = s1[i] + dp[i+1][s2.size()];

        for(int j = s2.size()-1 ; j >= 0 ; j --)
            dp[s1.size()][j] = s2[j] + dp[s1.size()][j+1];

        for(int i = s1.size()-1 ; i >= 0 ; i --)
            for(int j = s2.size()-1 ; j >= 0 ; j --){
                dp[i][j] = min(s1[i] + dp[i+1][j], s2[j] + dp[i][j+1]);
                if(s1[i] == s2[j])
                    dp[i][j] = min(dp[i][j], dp[i+1][j+1]);
            }

        return dp[0][0];
    }
};

int main() {

    cout << Solution().minimumDeleteSum("sea", "eat") << endl;
    cout << Solution().minimumDeleteSum("delete", "leet") << endl;

    return 0;
}