最长公共子序列(二)

class Solution:

    def __reConstructStr(self, s1:str, m:int, n:int, b:List[List[int]]) -> str:
        res = ""
        if m == 0&nbs***bsp;n == 0:
            return res

        if b[m][n] == 1:
            res += self.__reConstructStr(s1, m-1, n-1, b)
            res += s1[m-1]
        elif b[m][n] == 2:
            res += self.__reConstructStr(s1, m-1, n, b)
        elif b[m][n] == 3:
            res += self.__reConstructStr(s1, m, n-1, b)
        return res

    
    def LCS(self , s1: str, s2: str) -> str:
        # 定义dp[i][j]为s1前i个字符和s2前j个字符的最长公共子序列
        # 状态转移方程：if s1[i] == s2[j] then dp[i+1][j+1] = dp[i][j] + 1
        # if s1[i] != s2[j] then dp[i+1][j+1] = max(dp[i+1][j], dp[i][j+1])
        # 同时定义一个b[i][j]用来记录动态规划数组的计算方向
        m, n = len(s1), len(s2)
        dp = [[0 for _ in range(n+1)] for _ in range(m+1)]
        b = [[0 for _ in range(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] + 1
                    # 从对角线来
                    b[i][j] = 1
                else:
                    if dp[i-1][j] > dp[i][j-1]:
                        dp[i][j] = dp[i-1][j]
                        # 从上边来
                        b[i][j] = 2
                    else:
                        dp[i][j] = dp[i][j-1]
                        # 从左边来
                        b[i][j] = 3
        res = self.__reConstructStr(s1, m, n, b)
        return res if res else "-1"

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# longest common subsequence
# @param s1 string字符串 the string
# @param s2 string字符串 the string
# @return string字符串
#
class Solution:
    def LCS(self , s1: str, s2: str) -> str:
        ret = ''
        l1, l2 = len(s1), len(s2)
        matrix = [[''] * l2 for _ in s1]
        for i in range(l1):
            last, tmp = '', ''
            for j in range(l2):
                if s1[i] == s2[j]:
                    tmp = s2[j]
                    if i > 0 and j > 0:
                        last = matrix[i-1][j-1]
                if tmp and len(matrix[i-1][j]) < len(last + tmp):
                    matrix[i][j] = last + tmp
                else:
                    matrix[i][j] = matrix[i-1][j]
                if len(matrix[i][j]) > len(ret):
                    ret = matrix[i][j]
        return ret if ret else '-1'

class Solution:
    def LCS(self , s1: str, s2: str) -> str:
        if s1 is None or s2 is None:
            return '-1'
        len1 = len(s1)
        len2 = len(s2)
        dp = [[''] * (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] + s1[i -1]
                else:
                    dp[i][j] = dp[i][j-1] if len(dp[i][j-1]) > len(dp[i-1][j]) else dp[i-1][j]
        return dp[-1][-1] if dp[-1][-1] != '' else '-1'

class Solution:
    def LCS(self, s1, s2):
        l1, l2 = len(s1), len(s2)
        dst = [[''] * (l2 + 1) for _ in range(l1 + 1)]
        for i in range(1, l1 + 1):
            for j in range(1, l2 + 1):
                # 两个字符串当前位置字符相等，把当前字符加入公共子序列
                if s1[i - 1] == s2[j - 1]:
                    dst[i][j] = dst[i - 1][j - 1] + s1[i - 1]
                # 两字符串当前位置字符不相等，公共子序列取前面较长的一个
                else:
                    dst[i][j] = max(dst[i - 1][j], dst[i][j - 1], key=len)
        if not dst[l1][l2]:
            return -1
        else:
            return dst[l1][l2]

#
# longest common subsequence
# @param s1 string字符串 the string
# @param s2 string字符串 the string
# @return string字符串
#
class Solution:
    def LCS(self , s1 , s2 ):
        # write code here
        m, n = len(s1), len(s2)
        dp = [['']*(n+1) for _ in range(m+1)]   #m+1行，n+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:
                    if len(dp[i-1][j]) > len(dp[i][j-1]):
                        dp[i][j] = dp[i-1][j]
                    else:
                        dp[i][j] = dp[i][j-1]
        if dp[m][n] == '':
            return -1
        else:
            return dp[m][n]
        
        
        

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:
                    if len(dp[i - 1][j])>len(dp[i][j - 1]):
                        dp[i][j] =dp[i - 1][j]
                    else:
                        dp[i][j] =dp[i][j - 1]
        if dp[m][n]=='':
            return -1
        else:
            return dp[m][n]

class Solution(object):
    def longestCommonSubsequence(self, text1, text2):
        """
        :type text1: str
        :type text2: str
        :rtype: int
        """
        m, n = len(text1), len(text2)
        dp = [[0] * (n + 1) for _ in range(m + 1)]
        
        for i in range(1, m + 1):
            for j in range(1, n + 1):
                if text1[i - 1] == text2[j - 1]:
                    dp[i][j] = dp[i - 1][j - 1] + 1
                else:
                    dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]) 
        return dp[m][n]