代码随想录算法训练营第四十三天-115不同的子序列、583两个字符串的删除操作、72编辑距离
初步题解
115 不同的子序列
题目链接：(https://leetcode.cn/problems/distinct-subsequences/)
583 两个字符串的删除操作
题目链接：(https://leetcode.cn/problems/delete-operation-for-two-strings/)
-
确定 dp[i][j] 的含义：s 到 i - 1；t 到 j - 1 位置的删除相同需要的最小步数。
-
递推公式：如果当前位置元素相同：dp[i][j] = dp[i - 1][j - 1]; （即不加这个元素时的子序列个数 + 加上这个元素的子序列个数）， 如果当前位置元素不同：dp[i][j] = Math.min(dp[i - 1][j] + 1, dp[i][j - 1] + 1); （画图即当前位置的上左再去除一个元素并取较小值）。
-
dp 数组的初始化：dp[i][0] 、dp[0][j] 都是与元素个数有关。
-
遍历顺序：从上到下，从左到右。
-
打印 dp 数组（用于 debug）
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
| public int minDistance(String word1, String word2) {
int[][] dp = new int[word1.length() + 1][word2.length() + 1];
for (int i = 0; i < dp.length; i++) {
dp[i][0] = i;
}
for (int i = 0; i < dp[0].length; i++) {
dp[0][i] = i;
}
for (int i = 1; i <= word1.length(); i++) {
for (int j = 1; j <= word2.length(); 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, dp[i][j - 1] + 1);
}
}
}
System.out.println(Arrays.deepToString(dp));
return dp[word1.length()][word2.length()];
}
|
72 编辑距离
题目链接：(https://leetcode.cn/problems/edit-distance)
看解析
115 不同的子序列
解析：(https://programmercarl.com/0115.不同的子序列.html)
-
确定 dp[i][j] 的含义：s 到 i - 1；t 到 j - 1 位置的子序列个数。
-
递推公式：如果当前位置元素相同：dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j]; （即不加这个元素时的子序列个数 + 加上这个元素的子序列个数）， 如果当前位置元素不同：dp[i][j] = dp[i - 1][j];。
-
dp 数组的初始化：dp[i][0] 一定都是 1，因为也就是把以 i-1 为结尾的 s，删除所有元素，出现空字符串的个数就是 1。dp[0][j] 一定都是 0。dp[0][0] 应该是 1。
-
遍历顺序：从上到下，从左到右。
-
打印 dp 数组（用于 debug）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| public int numDistinct(String s, String t) {
int[][] dp = new int[s.length() + 1][t.length() + 1];
for (int i = 0; i < dp.length; i++) {
dp[i][0] = 1;
}
for (int i = 1; i <= s.length(); i++) {
for (int j = 1; j <= t.length(); 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];
}
}
}
System.out.println(Arrays.deepToString(dp));
return dp[s.length()][t.length()];
}
|
583 两个字符串的删除操作
解析：(https://programmercarl.com/0583.两个字符串的删除操作.html)
72 编辑距离
解析：(https://programmercarl.com/0072.编辑距离.html)
-
确定 dp[i][j] 的含义：word1 到 i - 1；word2 到 j - 1 位置的最小编辑数。
-
递推公式：需要确认四种情况：word1[i - 1] == word2[j - 1] 时，不操作；word1[i - 1] != word2[j - 1]，增删换。具体公式看代码。
-
dp 数组的初始化：dp[i][0] 、dp[0][j] 都是与元素个数有关，即删除所有元素。
-
遍历顺序：从上到下，从左到右。
-
打印 dp 数组（用于 debug）
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
| public int minDistance(String word1, String word2) {
int[][] dp = new int[word1.length() + 1][word2.length() + 1];
for (int i = 0; i < dp.length; i++) {
dp[i][0] = i;
}
for (int i = 0; i < dp[0].length; i++) {
dp[0][i] = i;
}
for (int i = 1; i <= word1.length(); i++) {
for (int j = 1; j <= word2.length(); j++) {
if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
dp[i][j] = dp[i - 1][j - 1];
} else {
dp[i][j] = Math.min(Math.min(dp[i - 1][j - 1], dp[i - 1][j]), Math.min(dp[i - 1][j], dp[i][j - 1])) + 1;
}
}
}
System.out.println(Arrays.deepToString(dp));
return dp[word1.length()][word2.length()];
}
|