「力扣」第 1143 题：最长公共子序列（中等）
给定两个字符串 text1 和 text2，返回这两个字符串的最长公共子序列。
一个字符串的 子序列 是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。
例如，”ace” 是 “abcde” 的子序列，但 “aec” 不是 “abcde” 的子序列。两个字符串的「公共子序列」是这两个字符串所共同拥有的子序列。若这两个字符串没有公共子序列，则返回 0。
示例 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 <= 1000
- 1 <= text2.length <= 1000
- 输入的字符串只含有小写英文字符。
方法：动态规划
最初的想法
「状态转移方程」是容易看明白的，但是总感觉说不太清楚。
「动态规划」就是填表格；
「状态」定义：
dp[i][j]表示前缀text1[:i]和 前缀text2[:j]的「最长公共子串」的长度，这里i和j都是包含的；「状态转移方程」的分类讨论：
如果
text1[i] == text2[j]，那么dp[i][j] == dp[i - 1][j - 1]；如果
text1[i] != text2[j]，那么dp[i][j]的值由两部分取较大者：考虑：
text1[:i - 1]和text2[:j]；考虑：
text1[:i]和text2[:j - 1]。这两者之中的最大者，是
dp[i][j]的值。
注意：这里要为了考虑清楚边界问题，需要设置一个特殊的状态 0，这是基于特殊用例一个非空字符串与空字符串而来的。为此，修改状态定义。
最终的想法
- 状态定义：
dp[i][j]表示长度为i的text1的前缀子串与长度为j的text2的前缀子串的「最长公共子串」的长度。注意：这里要考虑长度为0的前缀子串；
（类似考虑了长度为 0 的字符串的「状态」定义方式还有「力扣」第 10 题：正则表达式。）
- 状态转移方程：
$$
\text{dp}[i + 1][j + 1] =
\begin{cases}
\text{dp}[i][j] &\text{if} \ \text{text1}[i] = \text{text2}[j] \
\text{dp}[i + 1][j] \
\text{dp}[i][j + 1]
\end{cases}
$$
- 初始化：表格
dp的第 1 行和第 1 列均为 0。 - 输出：
dp[len1][len2]。
Java 代码：
public class Solution {
public int longestCommonSubsequence(String text1, String text2) {
int len1 = text1.length();
int len2 = text2.length();
char[] charArray1 = text1.toCharArray();
char[] charArray2 = text2.toCharArray();
// 字符串的问题多开一行，多开一列
int[][] dp = new int[len1 + 1][len2 + 1];
for (int i = 0; i <= len1; i++) {
dp[i][0] = 0;
}
for (int j = 0; j <= len2; j++) {
dp[0][j] = 0;
}
for (int i = 0; i < len1; i++) {
for (int j = 0; j < len2; j++) {
if (charArray1[i] == charArray2[j]) {
dp[i + 1][j + 1] = dp[i][j] + 1;
} else {
dp[i + 1][j + 1] = Math.max(dp[i + 1][j], dp[i][j + 1]);
}
}
}
return dp[len1][len2];
}
}复杂度分析：
- 时间复杂度：$O(MN)$，这里 $M$ 是字符串
text1的长度， $N$ 是字符串text2的长度； - 空间复杂度：$O(MN)$。
补充 1：如果不考虑边界，写出来的代码是这样的。可以对比一下，代码量会多一些，而且比较容易出错。
Java 代码：
public class Solution {
public int longestCommonSubsequence(String text1, String text2) {
int len1 = text1.length();
int len2 = text2.length();
int[][] dp = new int[len1][len2];
if (text1.charAt(0) == text2.charAt(0)) {
dp[0][0] = 1;
}
// 写第 1 行
for (int j = 1; j < len2; j++) {
dp[0][j] = dp[0][j - 1];
if (text1.charAt(0) == text2.charAt(j)) {
dp[0][j] = 1;
}
}
// 写第 1 列
for (int i = 1; i < len1; i++) {
dp[i][0] = dp[i - 1][0];
if (text1.charAt(i) == text2.charAt(0)) {
dp[i][0] = 1;
}
}
for (int i = 1; i < len1; i++) {
for (int j = 1; j < len2; j++) {
if (text1.charAt(i) == text2.charAt(j)) {
dp[i][j] = dp[i - 1][j - 1] + 1;
} else {
dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
}
}
}
return dp[len1 - 1][len2 - 1];
}
}补充 2：一个行之有效的办法，依然是手写一下，体会一下填表的过程，理解「状态转移方程」和「动态规划」。
发现了自己填表时候的错误，更能理解「状态转移方程」和细节，这就是所谓的「在错误中学习，印象更加深刻」。
Java 代码：
import java.util.Arrays;
public class Solution {
public int longestCommonSubsequence(String text1, String text2) {
int len1 = text1.length();
int len2 = text2.length();
char[] charArray1 = text1.toCharArray();
char[] charArray2 = text2.toCharArray();
// 字符串的问题多开一行，多开一列
int[][] dp = new int[len1 + 1][len2 + 1];
for (int i = 0; i <= len1; i++) {
dp[i][0] = 0;
}
for (int j = 0; j <= len2; j++) {
dp[0][j] = 0;
}
for (int i = 0; i < len1; i++) {
for (int j = 0; j < len2; j++) {
if (charArray1[i] == charArray2[j]) {
dp[i + 1][j + 1] = dp[i][j] + 1;
} else {
dp[i + 1][j + 1] = Math.max(dp[i + 1][j], dp[i][j + 1]);
}
}
}
// 以下是打印输出语句，不能提交到「力扣」测评器里
for (int i = 0; i <= len1; i++) {
System.out.println(Arrays.toString(dp[i]));
}
return dp[len1][len2];
}
public static void main(String[] args) {
Solution solution = new Solution();
String text1 = "abcde";
String text2 = "ace";
int res = solution.longestCommonSubsequence(text1, text2);
System.out.println(res);
}
}
输出：
[0, 0, 0, 0]
[0, 1, 1, 1]
[0, 1, 1, 1]
[0, 1, 2, 2]
[0, 1, 2, 2]
[0, 1, 2, 3]
3（本节完）
