网站建设应当注意哪些问题,常州天宁区做网站公司,智慧农业项目方案,wordpress页面自定义数据上传图片1143. 最长公共子序列 问题描述#xff1a;
给定两个字符串 text1 和 text2#xff0c;返回这两个字符串的最长 公共子序列 的长度。如果不存在公共子序列 #xff0c;返回 0 。
一个字符串的 子序列 是指这样一个新的字符串#xff1a;它是由原字符串在不改变字符的相对… 1143. 最长公共子序列 问题描述
给定两个字符串 text1 和 text2返回这两个字符串的最长 公共子序列 的长度。如果不存在公共子序列 返回 0 。
一个字符串的 子序列 是指这样一个新的字符串它是由原字符串在不改变字符的相对顺序的情况下删除某些字符也可以不删除任何字符后组成的新字符串。
例如ace 是abcde的子序列但 aec 不是abcde的子序列。 两个字符串的 公共子序列 是这两个字符串所共同拥有的子序列。
示例 1 输入text1 “abcde”, text2 “ace” 输出3 解释最长公共子序列是 “ace” 它的长度为 3 。 示例 2 输入text1 “abc”, text2 “abc” 输出3 解释最长公共子序列是 “abc” 它的长度为 3 。 提示
1 text1.length, text2.length 1000text1 和 text2 仅由小写英文字符组成。
问题分析
常见的题目了只是这个题目的子序列并不是严格的子序列是相对位置一样也算很显然是dp设假设dp[i][j] 表示字符串text1[0:i]和字符串text2[0:j]的最长公共子序列的长度现在讨论细节 (1) 很显然当i0 or j0时dp为0。 (2) text1[0:i] text2[0:j] 时很显然就上一个状态加上1即dp[i][j]dp[i-1][j-1]1 (3) text1[0:i] ! text2[0:j] 时竟然不相等那就text1和text2各自的上一个状态两者取最值就好了即dp[i][j]max(dp[i-1][j], dp[i][j-1])所以整体状态转移方差为
i0 or j0 : dp[i][j] 0
text1[i-1] text2[j-1]: dp[i][j] dp[i-1][j-1] 1
text1[i-1] ! text2[j-1]: dp[i][j] max(dp[i-1][j], dp[i][j-1])Python3实现
# Time :2023/09/01
# Author :Liu
# 动态规划class Solution:def longestCommonSubsequence(self, text1: str, text2: str) - 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] 1else:dp[i][j] max(dp[i-1][j], dp[i][j-1])return dp[m][n]举一反三
其实面试的时候大多数情况下会有所改动例如如果题目中的最长公共子串必须为严格连续的那该如何求解其实这个题目就是 LeetCode: 718. 最长重复子数组
这个时候其实可以转换成公共前缀或者公共后缀的问题设假设dp[i][j] 表示字符串text1[0:i]和字符串text2[0:j]的最长公共后缀串的长度现在讨论细节 (1) 很显然当i0 or j0时dp为0。 (2) text1[0:i] text2[0:j] 时很显然就上一个状态加上1即dp[i][j]dp[i-1][j-1]1 (3) text1[0:i] ! text2[0:j] 时不相等那就当前字符串text1[0:i]和text2[0:j] 没有公共后缀串所以就是0了即dp[i][j]0所以整体状态转移方差为
i0 or j0 : dp[i][j] 0
text1[i-1] text2[j-1]: dp[i][j] dp[i-1][j-1] 1
text1[i-1] ! text2[j-1]: dp[i][j] 0Python3实现
# Time :2023/09/01
# Author :Liu
# 动态规划class Solution:def longestCommonSubsequence2(self, text1, text2):m, n len(text1), len(text2)dp [[0] * (n 1) for _ in range(m 1)]ans, sub 0, # 最长公共子串长度最长公共子串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] 1else:dp[i][j] 0 # 这一步其实没必要本身就为0if ans dp[i][j]: # 更新最长子串ans dp[i][j]sub text1[i-ans: i]return ans, subif __name__ __main__:solu Solution()text1, text2 abcde, eahabcdprint(solu.longestCommonSubsequence2(text1, text2)) # (4, abcd)相关参考 题目链接 参考链接 声明 总结学习有问题或不当之处可以批评指正哦谢谢。
