磁力岛,电脑优化大师,太原百度网站快速排名,有趣实用的网站LeetCode-1143. 最长公共子序列【字符串 动态规划】 题目描述#xff1a;解题思路一#xff1a;动规五部曲解题思路二#xff1a;1维DP解题思路三#xff1a;0 题目描述#xff1a;
给定两个字符串 text1 和 text2#xff0c;返回这两个字符串的最长 公共子序列 的长度。… LeetCode-1143. 最长公共子序列【字符串 动态规划】 题目描述解题思路一动规五部曲解题思路二1维DP解题思路三0 题目描述
给定两个字符串 text1 和 text2返回这两个字符串的最长 公共子序列 的长度。如果不存在 公共子序列 返回 0 。
一个字符串的 子序列 是指这样一个新的字符串它是由原字符串在不改变字符的相对顺序的情况下删除某些字符也可以不删除任何字符后组成的新字符串。
例如“ace” 是 “abcde” 的子序列但 “aec” 不是 “abcde” 的子序列。 两个字符串的 公共子序列 是这两个字符串所共同拥有的子序列。
示例 1
输入text1 “abcde”, text2 “ace” 输出3 解释最长公共子序列是 “ace” 它的长度为 3 。 示例 2
输入text1 “abc”, text2 “abc” 输出3 解释最长公共子序列是 “abc” 它的长度为 3 。 示例 3
输入text1 “abc”, text2 “def” 输出0 解释两个字符串没有公共子序列返回 0 。
提示
1 text1.length, text2.length 1000 text1 和 text2 仅由小写英文字符组成。
解题思路一动规五部曲
确定dp数组dp table以及下标的含义 dp[i][j]长度为[0, i - 1]的字符串text1与长度为[0, j - 1]的字符串text2的最长公共子序列为dp[i][j]
有同学会问为什么要定义长度为[0, i - 1]的字符串text1定义为长度为[0, i]的字符串text1不香么
这样定义是为了后面代码实现方便如果非要定义为长度为[0, i]的字符串text1也可以我在 动态规划718. 最长重复子数组 (opens new window)中的「拓展」里 详细讲解了区别所在其实就是简化了dp数组第一行和第一列的初始化逻辑。
确定递推公式 主要就是两大情况 text1[i - 1] 与 text2[j - 1]相同text1[i - 1] 与 text2[j - 1]不相同
如果text1[i - 1] 与 text2[j - 1]相同那么找到了一个公共元素所以dp[i][j] dp[i - 1][j - 1] 1;
如果text1[i - 1] 与 text2[j - 1]不相同那就看看text1[0, i - 2]与text2[0, j - 1]的最长公共子序列 和 text1[0, i - 1]与text2[0, j - 2]的最长公共子序列取最大的。
即dp[i][j] max(dp[i - 1][j], dp[i][j - 1]);
dp数组如何初始化 先看看dp[i][0]应该是多少呢
test1[0, i-1]和空串的最长公共子序列自然是0所以dp[i][0] 0;
同理dp[0][j]也是0。
其他下标都是随着递推公式逐步覆盖初始为多少都可以那么就统一初始为0。 确定遍历顺序 从递推公式可以看出有三个方向可以推出dp[i][j]如图 那么为了在递推的过程中这三个方向都是经过计算的数值所以要从前向后从上到下来遍历这个矩阵。 举例推导dp数组 以输入text1 “abcde”, text2 “ace” 为例dp状态如图 最后红框dp[text1.size()][text2.size()]为最终结果
class Solution:def longestCommonSubsequence(self, text1: str, text2: str) - int:# 创建一个二维数组 dp用于存储最长公共子序列的长度dp [[0] * (len(text2) 1) for _ in range(len(text1) 1)]# 遍历 text1 和 text2填充 dp 数组for i in range(1, len(text1) 1):for j in range(1, len(text2) 1):if text1[i - 1] text2[j - 1]:# 如果 text1[i-1] 和 text2[j-1] 相等则当前位置的最长公共子序列长度为左上角位置的值加一dp[i][j] dp[i - 1][j - 1] 1else:# 如果 text1[i-1] 和 text2[j-1] 不相等则当前位置的最长公共子序列长度为上方或左方的较大值dp[i][j] max(dp[i - 1][j], dp[i][j - 1])# 返回最长公共子序列的长度return dp[len(text1)][len(text2)]# 同意
class Solution:def longestCommonSubsequence(self, text1: str, text2: str) - int:m, n len(text1), len(text2)dp [[0] * (n1) for _ in range(m1)]for i in range(1, m1):for j in range(1, n1):if text1[i-1] ! text2[j-1]:dp[i][j] max(dp[i-1][j], dp[i][j-1])else:dp[i][j] dp[i-1][j-1] 1return dp[-1][-1]时间复杂度O(nm) 空间复杂度O(nm)
解题思路二1维DP
class Solution:def longestCommonSubsequence(self, text1: str, text2: str) - int:m, n len(text1), len(text2)dp [0] * (n 1) # 初始化一维DP数组for i in range(1, m 1):prev 0 # 保存上一个位置的最长公共子序列长度for j in range(1, n 1):curr dp[j] # 保存当前位置的最长公共子序列长度if text1[i - 1] text2[j - 1]:# 如果当前字符相等则最长公共子序列长度加一dp[j] prev 1else:# 如果当前字符不相等则选择保留前一个位置的最长公共子序列长度中的较大值dp[j] max(dp[j], dp[j - 1])prev curr # 更新上一个位置的最长公共子序列长度return dp[n] # 返回最后一个位置的最长公共子序列长度作为结果时间复杂度O(nm) 空间复杂度O(n)
解题思路三0 时间复杂度O(n) 空间复杂度O(n)
