欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

LeetCode1143 最长公共子序列

程序员文章站 2024-01-01 12:30:40
文章目录一. 题目描述二. 解题思路三. 代码一. 题目描述给定两个字符串 text1 和 text2,返回这两个字符串的最长公共子序列的长度。一个字符串的 子序列 是指这样一个新的字符串:它是由原字符串在不改变字符的相对顺序的情况下删除某些字符(也可以不删除任何字符)后组成的新字符串。例如,“ace” 是 “abcde” 的子序列,但 “aec” 不是 “abcde” 的子序列。两个字符串的「公共子序列」是这两个字符串所共同拥有的子序列。若这两个字符串没有公共子序列,则返回 0。来源:力扣(...

一. 题目描述

给定两个字符串 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

上一篇:

下一篇: