最长公共子序列

描述

给定两个字符串str1和str2，输出两个字符串的最长公共子序列。如果最长公共子序列为空，则返回”-1”。目前给出的数据，仅仅会存在一个最长的公共子序列

示例1

输入：

"1A2C3D4B56","B1D23A456A"

返回值：

"123456"

示例2

输入：

"abc","def"

返回值：

"-1"

示例3

输入：

"abc","abc"

返回值：

"abc"

解答

如果单纯求长度就行，难点在于找到递推公式：

dp[i][j]表示s1[i]和s2[j]中的最长子串长度，显然如果s1[i]==s2[j]，则有，dp[i][j] = dp[i-1][j-1] + 1

class Solution:
    def LCS(self , s1 , s2 ):
        # write code here
        len1, len2 = len(s1), len(s2)
        dp = [[0 for j in range(len2+1)] for i in range(len1+1)]
        for i in range(1, len1+1):
            for j in range(1, len2+1):
                if s1[i-1] == s2[j-1] :
                    dp[i][j] = dp[i-1][j-1] + 1
                else:
                    # pay attention!!!
                    dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
        return dp[len1][len2]

如果需要返回最长子序列，建议画个dp图，找规律：

1、需要从右下往左上走

2、对于dp[i][j]=k ，必须要找到满足：dp[i-1][j]<k和dp[i][j-1]<k

class Solution:
    def LCS(self , s1 , s2 ):
        # write code here
        len1, len2 = len(s1), len(s2)
        dp = [[0 for j in range(len2+1)] for i in range(len1+1)]
        for i in range(1, len1+1):
            for j in range(1, len2+1):
                if s1[i-1] == s2[j-1] :
                    dp[i][j] = dp[i-1][j-1] + 1
                else:
                    # pay attention!!!
                    dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
        maxlen = dp[len1][len2]
        if maxlen == 0:
            return -1
        count = maxlen
        _str = []
        i,j = len1, len2
        while i>=1 and j>=1 and count>0:
            while  j>0 and dp[i][j-1] >= count:
                j -= 1
            while i>0 and dp[i-1][j] >= count:
                i -= 1
            _str.append(s1[i-1])
            j -= 1
            i -= 1
            count -= 1
        return "".join(_str[::-1])   

参考

https://leetcode-cn.com/problems/longest-common-subsequence