对于两个字符串求子序列的问题,都是用两个指针 ij 分别在两个字符串上移动,大概率是动态规划思路

labuladong-最长公共子序列

相关题目

1143. 最长公共子序列

583. 两个字符串的删除操作

712. 两个字符串的最小ASCII删除和

思路

定义dp(s1, i, s2, j)s1[i...]s2[j...]的最长公共子序列长度

goal: dp(s1, 0, s2, 0) 从零开始的最长公共子序列长度

base case: i == len(s1)j == len(s2) 由于相当于没有string,所以最长公共子序列长度为0

状态转移:

在选的情况下,即charAt[i] == charAt[j]时,状态转移:

状态转移_选

在不选的情况下可以从三种情况转移:

状态转移

但是其实只有情况一和情况二,因为情况三被情况一cover了

1143. 最长公共子序列

模板题

代码:

自顶向下的递归解法:

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
class Solution {
String text1, text2;
int m, n;
int[][] memo;
public int longestCommonSubsequence(String text1, String text2) {
m = text1.length();
n = text2.length();
// 初始化 memo 为了消除重复子问题
memo = new int[m][n];
for (int i = 0; i < m; i++) {
Arrays.fill(memo[i], -1);
}
this.text1 = text1;
this.text2 = text2;
return dp(0, 0);
}
private int dp(int i, int j) {
if (i == m || j == n) return 0;
if (memo[i][j] != -1) return memo[i][j];
if (text1.charAt(i) == text2.charAt(j)) {
memo[i][j] = dp(i + 1, j + 1) + 1;
} else {
memo[i][j] = Math.max(
dp(i + 1, j),
dp(i, j + 1)
);
}
return memo[i][j];
}
}

自底向上的迭代解法:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public int longestCommonSubsequence(String s1, String s2) {
int m = s1.length(), n = s2.length();
int[][] dp = new int[m + 1][n + 1];
// 定义:s1[0..i-1] 和 s2[0..j-1] 的 lcs 长度为 dp[i][j]
// 目标:s1[0..m-1] 和 s2[0..n-1] 的 lcs 长度,即 dp[m][n]
// base case: dp[0][..] = dp[..][0] = 0

for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
// 现在 i 和 j 从 1 开始,所以要减一
if (s1.charAt(i - 1) == s2.charAt(j - 1)) {
// s1[i-1] 和 s2[j-1] 必然在 lcs 中
dp[i][j] = 1 + dp[i - 1][j - 1];
} else {
// s1[i-1] 和 s2[j-1] 至少有一个不在 lcs 中
dp[i][j] = Math.max(dp[i][j - 1], dp[i - 1][j]);
}
}
}

return dp[m][n];
}
}

583. 两个字符串的删除操作

变换一下思路,我们要的就是让他们成为他们的公共子序列,问的是需要到达公共子序列所需要的步数:

word1.length - LCS.length + word2.length - LCS.length

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
class Solution {
String word1, word2;
int m, n;
int[][] memo;
public int minDistance(String word1, String word2) {
m = word1.length();
n = word2.length();
// 初始化 memo 为了消除重复子问题
memo = new int[m][n];
for (int i = 0; i < m; i++) {
Arrays.fill(memo[i], -1);
}
this.word1 = word1;
this.word2 = word2;
int lcsLength = dp(0, 0);
return (m - lcsLength) + (n - lcsLength);
}

private int dp(int i, int j) {
if (i == m || j == n) return 0;
if (memo[i][j] != -1) return memo[i][j];
if (word1.charAt(i) == word2.charAt(j)) {
memo[i][j] = dp(i + 1, j + 1) + 1;
} else {
memo[i][j] = Math.max(
dp(i + 1, j),
dp(i, j + 1)
);
}
return memo[i][j];
}
}