友情支持
如果您觉得这个笔记对您有所帮助，看在D瓜哥码这么多字的辛苦上，请友情支持一下，D瓜哥感激不尽，😜
|
|
有些打赏的朋友希望可以加个好友，欢迎关注D 瓜哥的微信公众号，这样就可以通过公众号的回复直接给我发信息。
公众号的微信号是: jikerizhi。因为众所周知的原因，有时图片加载不出来。 如果图片加载不出来可以直接通过搜索微信号来查找我的公众号。 |
1143. 最长公共子序列
给定两个字符串 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仅由小写英文字符组成。
思路分析
递归公式大概如下：
这个解法也可以用来解决 300. 最长递增子序列。
|
对比 718. 最长重复子数组 和 1143. 最长公共子序列 两道题的差异：
|
-
一刷
-
二刷
-
三刷（暴力破解）
-
三刷（备忘录）
-
三刷（动态规划）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
/**
* @author D瓜哥 · https://www.diguage.com
* @since 2025-04-21 20:25:23
*/
public int longestCommonSubsequence(String t, String s) {
int m = t.length(), n = s.length();
int[][] dp = new int[m + 1][n + 1];
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
if (t.charAt(i - 1) == s.charAt(j - 1)) {
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[m][n];
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
/**
* @author D瓜哥 · https://www.diguage.com
* @since 2025-10-07 21:27:54
*/
public int longestCommonSubsequence(String text1, String text2) {
int m = text1.length();
int n = text2.length();
int[][] dp = new int[m + 1][n + 1];
for (int r = 1; r <= m; r++) {
for (int c = 1; c <= n; c++) {
if (Objects.equals(text1.charAt(r - 1), text2.charAt(c - 1))) {
dp[r][c] = dp[r - 1][c - 1] + 1;
} else {
dp[r][c] = Math.max(dp[r - 1][c], dp[r][c - 1]);
}
}
}
return dp[m][n];
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
/**
* 暴力破解（18/47）
* @author D瓜哥 · https://www.diguage.com
* @since 2025-12-30 20:23:25
*/
public int longestCommonSubsequence(String text1, String text2) {
return dfs(text1.toCharArray(), text1.length() - 1, text2.toCharArray(), text2.length() - 1);
}
private int dfs(char[] a, int ai, char[] b, int bi) {
if (ai < 0 || bi < 0) {
return 0;
}
if (a[ai] == b[bi]) {
return dfs(a, ai - 1, b, bi - 1) + 1;
} else {
return Math.max(dfs(a, ai - 1, b, bi), dfs(a, ai, b, bi - 1));
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
/**
* 暴力破解（18/47）→ 备忘录（5.67%）
*
* @author D瓜哥 · https://www.diguage.com
* @since 2025-12-30 20:23:25
*/
public int longestCommonSubsequence(String text1, String text2) {
int[][] memo = new int[text1.length()][text2.length()];
for (int[] ints : memo) {
Arrays.fill(ints, -1);
}
return dfs(text1.toCharArray(), text1.length() - 1, text2.toCharArray(), text2.length() - 1, memo);
}
private int dfs(char[] a, int ai, char[] b, int bi, int[][] memo) {
if (ai < 0 || bi < 0) {
return 0;
}
if (memo[ai][bi] >= 0) {
return memo[ai][bi];
}
int result = 0;
if (a[ai] == b[bi]) {
result = dfs(a, ai - 1, b, bi - 1, memo) + 1;
} else {
result = Math.max(dfs(a, ai - 1, b, bi, memo), dfs(a, ai, b, bi - 1, memo));
}
memo[ai][bi] = result;
return result;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/**
* 暴力破解（18/47）→ 备忘录（5.67%）→ 动态规划（87.84%）
*
* @author D瓜哥 · https://www.diguage.com
* @since 2025-12-30 20:37:06
*/
public int longestCommonSubsequence(String text1, String text2) {
int[][] dp = new int[text1.length() + 1][text2.length() + 1];
char[] ac = text1.toCharArray();
char[] bc = text2.toCharArray();
for (int i = 0; i < text1.length(); i++) {
for (int j = 0; j < text2.length(); j++) {
if (ac[i] == bc[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[text1.length()][text2.length()];
}