【leetcode】712. Minimum ASCII Delete Sum for Two Strings

题目如下：

解题思路：本题和【leetcode】583. Delete Operation for Two Strings 类似，区别在于word1[i] != word2[j]的时候，是删除word1[i]还是word2[j]取决于min(dp[i-1][j]+ord(word1[i-1]),dp[i][j-1]+ord(word2[j-1]))。

代码如下：

class Solution(object):

    def minimumDeleteSum(self, s1, s2):

        """

        :type s1: str

        :type s2: str

        :rtype: int

        """

        word1 = s1

        word2 = s2

        if len(word1) == 0 or len(word2) == 0:

            return abs(len(word2) - len(word1))

        dp = [[0 for x in range(len(word2)+1)] for x in range(len(word1)+1)]

        w1_ascii = 0

        w2_ascii = 0

        for i in xrange(1,len(word1)+1):

            w1_ascii += ord(word1[i-1])

            dp[i][0] = w1_ascii

        for j in xrange(1,len(word2)+1):

            w2_ascii += ord(word2[j-1])

            dp[0][j] = w2_ascii

        for i in xrange(1,len(word1)+1):

            for j in xrange(1,len(word2)+1):

                if word1[i-1] == word2[j-1]:

                    dp[i][j] = dp[i-1][j-1]

                else:

                    dp[i][j] = min(dp[i-1][j]+ord(word1[i-1]),dp[i][j-1]+ord(word2[j-1]))

        return dp[-1][-1]

巴特西

【leetcode】712. Minimum ASCII Delete Sum for Two Strings

最新文章

热门文章