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

#
# longest common subsequence
# @param s1 string字符串 the string
# @param s2 string字符串 the string
# @return string字符串
#
'''

递归操作会超过python的最大迭代次数
"RuntimeError: maximum recursion depth exceeded in comparison 
出现原因: python默认迭代次数有限(大概是1000左右)

class Solution:
    def LCs(self,s1,s2):
        if len(s1)==0 or len(s2)==0:
            return ''
        if s1[-1]==s2[-1]:
            return self.LCs(s1[:-1],s2[:-1])+s1[-1]
        ls1=self.LCs(s1,s2[:-1])
        ls2=self.LCs(s1[:-1],s2)
        if len(ls1)>len(ls2):
            return ls1
        else:
            return ls2
    def LCS(self , s1 , s2 ):
        # write code here
        x = self.LCs(s1,s2)
        if x=='':
            return '-1'
        else:
            return x

'''



'''
参考：
https://blog.csdn.net/hrn1216/article/details/51534607
https://leetcode-cn.com/problems/qJnOS7
'''

class Solution:
    def LCS(self , s1 , s2 ):
        # write code here
        m,n=len(s1),len(s2)
        dp=[['']*(n+1) for _ in range(m+1)]
        for i in range(1,m+1):
            for j in range(1,n+1):
                if s1[i-1]==s2[j-1]:
                    dp[i][j]=dp[i-1][j-1]+s1[i-1]
                else:
                    ls1=dp[i][j-1]
                    ls2=dp[i-1][j]
                    if len(ls1)>len(ls2):
                        dp[i][j]=ls1
                    else:
                        dp[i][j]=ls2
        if dp[m][n]=='':
            return '-1'
        else:
            return dp[m][n]