题解 | #最长公共子序列-II#

'''
解题思路：
动态规划算法，
dp[i][j]定义为：str1在索引i处及之前位置，str2在索引j处及之前位置，存在公共子序列的最大长度
               需要回溯取依据取公共子序列字符
1、当i==0 | j==0：
   (a)当str1[i] == str2[j]，dp[i][j] = 1
   (b)当str1[i] != str2[j]，dp[i][j] = max(dp[i-1][j], dp[i][j-1])
2、其它情况：
   (c)当str1[i] == str2[j]，dp[i][j] = dp[i-1][j-1] + 1
   (d)当str1[i] != str2[j]，dp[i][j] = max(dp[i-1][j], dp[i][j-1])
#=============================================================================================
'''
#
# @param str1 string字符串 the string
# @param str2 string字符串 the string
# @return string字符串
#
class Solution:
    def LCS(self , str1 , str2 ):
        # write code here
        if str1 == '' or str2 == '':
            return '-1'       

        r = len(str1)
        c = len(str2)
        dp = [[0]*(c+1) for _ in range(r+1)]
        for i in range(1,1+r):
            for j in range(1,1+c):
                if (i==1 or j==1):
                    #print('A--',i,j)
                    if str1[i-1]==str2[j-1]:                    
                        dp[i][j] = 1
                    else:
                        dp[i][j] = max(dp[i][j-1],dp[i-1][j])
                else:
                    #print('B--',i,j)
                    if str1[i-1]==str2[j-1]:  
                        dp[i][j] = dp[i-1][j-1]+1
                    else:
                        dp[i][j] = max(dp[i][j-1],dp[i-1][j])
        #for i in dp:
        #    print(i)

        i = r
        j = c
        substr = ''
        while i>=1 and j>=1:
            if str1[i-1]==str2[j-1]:
                substr += str1[i-1]
                i -= 1
                j -= 1                
            else:
                if dp[i-1][j]>dp[i][j-1]:
                    i -= 1
                else:
                    j -= 1

        #print(substr[::-1])

        if substr != '':
            return substr[::-1]
        else:
            return '-1'


str1 = '1A2C3D4B56'
str2 = 'B1D23A456A'
s = Solution()
print(s.LCS(str1,str2))  # 123456