1143. 最长公共子序列 #
- 标签:字符串、动态规划
- 难度:中等
题目大意 #
描述:给定两个字符串 text1
和 text2
。
要求:返回两个字符串的最长公共子序列的长度。如果不存在公共子序列,则返回 0
。
说明:
- 子序列:原字符串在不改变字符的相对顺序的情况下删除某些字符(也可以不删除任何字符)后组成的新字符串。
- 公共子序列:两个字符串所共同拥有的子序列。
- $1 \le text1.length, text2.length \le 1000$。
text1
和text2
仅由小写英文字符组成。
示例:
|
|
解题思路 #
思路 1:动态规划 #
1. 定义状态 #
定义状态 dp[i][j]
表示为:前 i
个字符组成的字符串 str1
与前 j
个字符组成的字符串 str2
的最长公共子序列长度为 dp[i][j]
。
2. 状态转移方程 #
双重循环遍历字符串 text1
和 text2
,则状态转移方程为:
- 如果
text1[i - 1] == text2[j - 1]
,则说明找到了一个公共字符,此时dp[i][j] = dp[i - 1][j - 1] + 1
。 - 如果
text1[i - 1] != text2[j - 1]
,则dp[i][j]
需要考虑以下两种情况,取两种情况中最大的那种:dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
。text1
前i - 1
个字符组成的字符串str1
与text2
前j
个字符组成的str2
的最长公共子序列长度,即dp[i - 1][j]
。text1
前i
个字符组成的字符串str1
与text2
前j - 1
个字符组成的 str2 的最长公共子序列长度,即dp[i][j - 1]
。
3. 初始化 #
初始状态下,默认前 i
个字符组成的字符串 str1
与前 j
个字符组成的字符串 str2
的最长公共子序列长度为 0
,即 dp[i][j] = 0
。
4. 最终结果 #
根据状态定义,最后输出 dp[sise1][size2]
(即 text1
与 text2
的最长公共子序列长度)即可,其中 size1
、size2
分别为 text1
、text2
的字符串长度。
思路 1:动态规划代码 #
|
|
思路 1:复杂度分析 #
- 时间复杂度:$O(n^2)$。两重循环遍历的时间复杂度是 $O(n^2)$,所以总的时间复杂度为 $O(n^2)$。
- 空间复杂度:$O(n^2)$。用到了二维数组保存状态,所以总体空间复杂度为 $O(n^2)$。