题解 | 最长公共子序列(二)

class Solution:
    def LCS(self, s1: str, s2: str) -> str:
        # 去除字符串中的空格、换行符和逗号
        s1 = ''.join([char for char in s1 if char not in (' ', '\n', ',')])
        s2 = ''.join([char for char in s2 if char not in (' ', '\n', ',')])

        # 如果任意一个字符串为空，直接返回 -1
        if not s1 or not s2:
            return "-1"

        # 获取两个字符串的长度
        m, n = len(s1), len(s2)
        # 创建一个二维数组 dp 用于记录公共子序列的长度
        dp = [[0] * (n + 1) for _ in range(m + 1)]

        # 填充 dp 数组
        for i in range(1, m + 1):
            for j in range(1, n + 1):
                if s1[i - 1] == s2[j - 1]:
                    # 如果当前字符相等，则公共子序列长度加 1
                    dp[i][j] = dp[i - 1][j - 1] + 1
                else:
                    # 如果当前字符不相等，则取上方和左方的最大值
                    dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])

        # 如果最长公共子序列长度为 0，返回 -1
        if dp[m][n] == 0:
            return "-1"

        # 回溯构建最长公共子序列
        result = []
        i, j = m, n
        while i > 0 and j > 0:
            if s1[i - 1] == s2[j - 1]:
                # 如果当前字符相等，将其添加到结果中，并向左上方移动
                result.append(s1[i - 1])
                i -= 1
                j -= 1
            elif dp[i - 1][j] > dp[i][j - 1]:
                # 如果上方的值更大，向上移动
                i -= 1
            else:
                # 如果左方的值更大，向左移动
                j -= 1

        # 反转结果列表并转换为字符串
        result.reverse()
        return ''.join(result)

逆天豆包