动态规划——编辑距离 问题汇总
判断子序列
给定字符串 s 和 t ，判断 s 是否为 t 的子序列
https://leetcode.cn/problems/is-subsequence/
dp[i][j]表示 s[0...i-1]是否为t[0...j-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
| class Solution {
public boolean isSubsequence(String s, String t) {
if (s.length() > t.length()) {
return false;
}
int N = t.length();
int M = s.length();
char[] tc = t.toCharArray();
char[] sc = s.toCharArray();
boolean[][] dp = new boolean[N+1][M+1];
for (int i = 0; i <= N; i++) {
dp[i][0] = true;
}
for (int i = 1; i <= M; i++) {
dp[0][i] = false;
}
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= M ; j++) {
if (tc[i-1] == sc[j-1]) {
dp[i][j] = dp[i-1][j-1];
} else {
dp[i][j] = dp[i-1][j];
}
}
}
return dp[N][M];
}
}
|
dp数组变为int[][]类型，即为求t到s的删除距离
判断子序列问题优化：空间压缩
当dp公式只与上一层有关时，可以将二维dp数组优化为一维dp数组，降低空间复杂度
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 boolean isSubsequence(String s, String t) {
if (s.length() > t.length()) {
return false;
}
int N = t.length();
int M = s.length();
char[] sc = s.toCharArray();
char[] tc = t.toCharArray();
boolean[] dp = new boolean[M+1];
dp[0] = true;
for (int i = 1; i <= M; i++) {
dp[i] = false;
}
for (int i = 1; i <= N; i++) {
for (int j = M; j >= 1; j--) {
if (sc[j-1] == tc[i-1]) {
dp[j] = dp[j-1];
}
}
}
return dp[M];
}
}
|
删除成为子串
给定两个字符串s1和s2，问s2最少删除多少字符可以成为s1的子串？比如 s1 =
"abcde"，s2 = "axbc"，s2删掉'x'即可，返回1
思路：求s1的所有子串，求s2到每个子串的删除距离（同上题）
思考点：如何复用dp数组
Tips：具有相同前缀的s1的子串，可以共用一个dp数组，即在求一次dp方程时，一次性求出很多s1子串
1
2
3
4
5
| public Solution {
public int minCost(String s1, String s2) {
}
}
|
不同的子序列
给定一个字符串 s 和一个字符串 t ，计算在 s 的子序列中 t
出现的个数
https://leetcode.cn/problems/distinct-subsequences/
dp[i][j]：以i-1为结尾的s子序列中出现以j-1为结尾的t的个数
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
| class Solution {
public int numDistinct(String s, String t) {
if (s.length() < t.length()) {
return 0;
}
int N = s.length();
int M = t.length();
int[][] dp = new int[N+1][M+1];
for (int i = 0; i <= N; i++) {
dp[i][0] = 1;
}
for (int i = 1; i <= M; i++) {
dp[0][i] = 0;
}
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= M; j++) {
if (s.charAt(i-1) == t.charAt(j-1)) {
dp[i][j] = dp[i-1][j-1] + dp[i-1][j];
} else {
dp[i][j] = dp[i-1][j];
}
}
}
return dp[N][M];
}
}
|
同样可以用空间压缩优化，与第一题类似
两个字符串的删除操作
给定两个单词 word1 和 word2 ，返回使得 word1 和 word2
相同所需的最小步数。每步
可以删除任意一个字符串中的一个字符。
https://leetcode.cn/problems/delete-operation-for-two-strings/
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| class Solution {
public int minDistance(String word1, String word2) {
int N = word1.length();
int M = word2.length();
int[][] dp = new int[N+1][M+1];
for (int i = 0; i <= N; i++) {
dp[i][0] = i;
}
for (int i = 0; i <= M; i++) {
dp[0][i] = i;
}
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= M; j++) {
if (word1.charAt(i-1) == word2.charAt(j-1)) {
dp[i][j] = dp[i-1][j-1];
} else {
dp[i][j] = Math.min(dp[i-1][j-1] + 2, Math.min(dp[i-1][j] + 1, dp[i][j-1] + 1));
}
}
}
return dp[N][M];
}
}
|
编辑距离
给你两个单词 word1 和 word2， 请返回将 word1
转换成 word2 所使用的最少操作数
。你可以对一个单词进行如下三种操作：插入一个字符，删除一个字符，替换一个字符
https://leetcode.cn/problems/edit-distance/
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
| class Solution {
public int minDistance(String word1, String word2) {
int N = word1.length();
int M = word2.length();
char[] s = word1.toCharArray();
char[] t = word2.toCharArray();
int[][] dp = new int[N+1][M+1];
for (int i = 0; i <= N; i++) {
dp[i][0] = i;
}
for (int i = 0; i <= M; i++) {
dp[0][i] = i;
}
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= M; j++) {
if (s[i-1] == t[j-1]) {
dp[i][j] = dp[i-1][j-1];
} else {
dp[i][j] = Math.min(dp[i-1][j-1], Math.min(dp[i-1][j], dp[i][j-1])) + 1;
}
}
}
return dp[N][M];
}
}
|
总结
本文汇总了动态规划中常见的编辑距离问题，通过对每个问题的分析，可以发现：
- dp[i][j]
的含义一般都表示在s[0...i-1]与t[0...j-1]情况下的问题所求
- 边界一般都是考虑在dp[i][0]与dp[0][j]下的值
- dp方程具有很强的规律性，即在 s[i-1] 是否等于 t[j-1]
的两种情况下，考虑dp方程是什么
- 都可以使用空间压缩方法进行空间复杂度的优化