DP with python


  • 0
    E
    class Solution(object):
        def minimumDeleteSum(self, s1, s2):
            """
            :type s1: str
            :type s2: str
            :rtype: int
            """
            dp,s1_ascii,s2_ascii,f=[[0 for i in range(len(s2)+1)] for j in range(len(s1)+1)],0,0,0
            for i in range(1,len(s1)+1):
                s1_ascii+=ord(s1[i-1])
                for j in range(1,len(s2)+1):
                    if not f:s2_ascii+=ord(s2[j-1])
                    if s1[i-1]==s2[j-1]:dp[i][j]=dp[i-1][j-1]+ord(s1[i-1])
                    else:dp[i][j]=max(dp[i-1][j],dp[i][j-1])
                f=1
            return s1_ascii+s2_ascii-2*dp[i][j]
    

Log in to reply
 

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