LeetCode1143 最长公共子序列

文章目录

一. 题目描述

给定两个字符串 text1 和 text2，返回这两个字符串的最长公共子序列的长度。

一个字符串的 子序列 是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。
例如，“ace” 是 “abcde” 的子序列，但 “aec” 不是 “abcde” 的子序列。两个字符串的「公共子序列」是这两个字符串所共同拥有的子序列。

若这两个字符串没有公共子序列，则返回 0。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/longest-common-subsequence
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

二. 解题思路

思路： 动态规划

假定两个字符串为s1和s2。

从s1中一次获取每个元素，判断该元素是否在s2中。假定当前元素在s1中的索引为index

1）若不存在： 状态转移为 lcs(s1[index+1:], s2)

2）若存在: 假定在s2中的索引为index2. 又分为两种情况：

• 该元素放在公共子序列 状态转移为 1+lcs(s1[index+1:], s1[index2+1:])
• 该元素不放在公共子序列 状态转移为 lcs(s1[index+1:], s2)

终止条件 : 当s1或者s2为空 返回0

三. 代码

def lcs(string1: str, string2: str):
    if not string1 or not string2:
        return 0
    else:
        for i in range(len(string1)):
            if string1[i] not in string2:
                return lcs(string1[i+1:], string2)
            else:
                index2 = string2.index(string1[i])
                return max(1+lcs(string1[i+1:], string2[index2+1:]), lcs(string1[i+1:], string2))


#  这里延伸下，得到最长公共子序列（答案可能不唯一）
def get_lcs(string1: str, string2: str):
    record = []
    if not string1 or not string2:
        return ''
    else:
        for i in range(len(string1)):
            if string1[i] in string2:
                index2 = string2.index(string1[i])
                if 1+lcs(string1[i+1:], string2[index2+1:]) > lcs(string1[i+1:], string2):
                    record.append(string1[i])
                    string2 = string2[index2+1:]
        return ''.join(record)


if __name__ == "__main__":
    s1 = 'acsdasd'
    s2 = 'aasdsad'
    print(lcs(s1, s2))
    print(get_lcs(s1, s2))

本文地址：https://blog.csdn.net/weixin_43849063/article/details/111937102