1.题目描述
1143. 最长公共子序列
给定两个字符串 text1 和 text2，返回这两个字符串的最长公共子序列。
一个字符串的 子序列 是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。
例如，”ace” 是 “abcde” 的子序列，但 “aec” 不是 “abcde” 的子序列。两个字符串的「公共子序列」是这两个字符串所共同拥有的子序列。
若这两个字符串没有公共子序列，则返回 0。
示例 1:
1
2
3
| 输入：text1 = "abcde", text2 = "ace"
输出：3
解释：最长公共子序列是 "ace"，它的长度为 3。
|
示例 2:
1
2
3
| 输入：text1 = "abc", text2 = "abc"
输出：3
解释：最长公共子序列是 "abc"，它的长度为 3。
|
示例 3:
1
2
3
| 输入：text1 = "abc", text2 = "def"
输出：0
解释：两个字符串没有公共子序列，返回 0。
|
提示:
1 <= text1.length <= 10001 <= text2.length <= 1000
输入的字符串只含有小写英文字符。
2.代码实现
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
31
32
33
34
35
36
37
38
39
| class Solution {
public int longestCommonSubsequence(String text1, String text2) {
//特殊情况
if (text1.length() == 0 || text2.length() == 0){
return 0;
}
//存储str1对应长度子字符串和str2对应长度子字符串最长共同子序列
int[][] max_length = new int[text1.length()][text2.length()];
//System.out.println(max_length.length);
//初始化一些值
for (int i = 0; i < text1.length(); i++) {
for (int j = 0; j < 1; j++) {
max_length[i][j] = text1.charAt(i) == text2.charAt(j) ? 1 : 0;
if (max_length[i][j] == 0 && i > 0){
max_length[i][j] = max_length[i-1][j];
}
}
}
for (int i = 0; i < 1; i++) {
for (int j = 0; j < text2.length(); j++) {
max_length[i][j] = text1.charAt(i) == text2.charAt(j) ? 1 : 0;
if (max_length[i][j] == 0 && j > 0){
max_length[i][j] = max_length[i][j-1];
}
}
}
//初始化其他位置的值
for (int i = 1; i < text1.length(); i++) {
for (int j = 1; j < text2.length(); j++) {
max_length[i][j] = text1.charAt(i) == text2.charAt(j) ? max_length[i-1][j-1]+1 : Math.max(max_length[i-1][j],max_length[i][j-1]);
}
}
return max_length[text1.length()-1][text2.length()-1];
}
}
|
代码思路：
- 第一行数据分别代表B和A的最长公共子序列，BD和A的最长公共子序列，BDC和A的最长公共子序列，。。。
- 第一列数据分别代表A和B的最长公共子序列，AB和B的最长公共子序列，ABC和B的最长公共子序列，。。。
- 之后的数据需要判断当前位置是否两个对应字符是否相同。
- 不相同的情况：比如BD和AB的最长公共子序列，此时需要比较D和B是否相同，如果不相同那么就需要在B和AB的最长公共子序列和BD和A的最长公共子序列两者之间选择最大的。
- 相同的情况：比如BDC和ABC的最长公共子序列。由于C是共同的子序列，那么我们只需要找到BD和AB的最长公共子序列，BDC和ABC的最长公共子序列就是在BD和AB的最长公共子序列的基础上+1。
