LCS variation solution, python & c++


  • 2
    Z

    to get the minimal cost, we need to find the common subsequences, and among all the common subsequences, we need to find the minimal cost.

    it is very like to find the longest common subsequence, but this time, we need to find the max ascii common subsequence, then the minimal cost is the two fixed ascii sum of two origin strings, minus the max ascii common subsequence we have found.

    python code:

    class Solution(object):
        def minimumDeleteSum(self, s1, s2):
            """
            :type s1: str
            :type s2: str
            :rtype: int
            """
            l1 = len(s1)
            l2 = len(s2)
            dp = [[0] * (l2 + 1) for i in xrange(l1 + 1)]
            for i in xrange(l1):
                for j in xrange(l2):
                    if s1[i] == s2[j]:
                        dp[i+1][j+1] = dp[i][j] + ord(s1[i]) * 2
                    else:
                        dp[i+1][j+1] = max(dp[i+1][j], dp[i][j+1])
            n1 = sum(ord(c) for c in s1)
            n2 = sum(ord(c) for c in s2)
            return n1 + n2 - dp[l1][l2]
    

    c++ code:

    class Solution {
    public:
        int minimumDeleteSum(string s1, string s2) {
            int dp[1001][1001] = {0};
            for ( int i = 0; i < s1.size(); ++i ) {
                for ( int j = 0; j < s2.size(); ++j ) {
                    if ( s1[i] == s2[j] ) {
                        dp[i+1][j+1] = dp[i][j] + int(s1[i]) * 2;
                    } else {
                        dp[i+1][j+1] = max(dp[i+1][j], dp[i][j+1]);
                    }
                }
            }
            int n1 = accumulate(s1.begin(), s1.end(), 0);
            int n2 = accumulate(s2.begin(), s2.end(), 0);
            return n1 + n2 - dp[s1.size()][s2.size()];
        }
    };
    

  • 0

    Just a little rewrite. The one thing I think is really better is that I multiply by 2 only once, at the end.

    def minimumDeleteSum(self, s, t):
        m, n = len(s), len(t)
        dp = [[0] * (n+1) for _ in range(m+1)]
        for i, c in enumerate(s):
            for j, d in enumerate(t):
                dp[i+1][j+1] = dp[i][j] + ord(c) if c == d else max(dp[i][j+1], dp[i+1][j])
        return sum(map(ord, s + t)) - 2 * dp[m][n]

  • -1

    And somewhat golfed more space-efficient Python 3 versions:

    def minimumDeleteSum(self, s, t):
        a = [0] * (len(t) + 1)
        for c in s:
            a, b = [0], a
            for d, x, y, z in zip(t, b, b[1:], a):
                a += x + ord(c) if c == d else max(y, z),
        return sum(map(ord, s + t)) - 2 * a[-1]
    

    and

    def minimumDeleteSum(self, s, t):
        a = [0] * (len(t) + 1)
        for c in s:
            a, b = [0], a
            for d, x, y in zip(t, b, map(max, b[1:], a)):
                a += x + ord(c) if c == d else y,
        return sum(map(ord, s + t)) - 2 * a[-1]
    

    and a particularly lazy one:

    def minimumDeleteSum(self, s, t):
        a = [0] * (len(t) + 1)
        for c in s:
            a, b = [0], a
            a += (x + ord(c) if c == d else y for d, x, y in zip(t, b, map(max, b[1:], a)))
        return sum(map(ord, s + t)) - 2 * a[-1]

Log in to reply
 

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