编辑距离
72. 编辑距离 - 力扣（LeetCode）
动态规划： dp[i][j] 代表 word1 到 i 位置转换成 word2 到 j 位置需要最少步数
所以，
当 word1[i] == word2[j]，dp[i][j] = dp[i-1][j-1]；
当 word1[i] != word2[j]，dp[i][j] = min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1]) + 1
其中，dp[i-1][j-1] 表示替换操作，dp[i-1][j] 表示删除操作，dp[i][j-1] 表示插入操作。
注意，针对第一行，第一列要单独考虑，我们引入 '' 下图所示：
1. 初始化：将 `dp[0][j]` 和 `dp[i][0]` 初始化为相应的初始值。`dp[0][j]` 表示将空字符串转换为 `word2` 的前 `j` 个字符所需的最小编辑距离，即插入操作。同理，`dp[i][0]` 表示将 `word1` 的前 `i` 个字符转换为空字符串所需的最小编辑距离，即删除操作。 2. 状态转移：对于 `dp[i][j]`，考虑 `word1` 的第 `i` 个字符和 `word2` 的第 `j` 个字符：
如果 `word1.charAt(i - 1) == word2.charAt(j - 1)`，说明当前字符相同，不需要进行操作，所以 `dp[i][j] = dp[i - 1][j - 1]`。如果 `word1.charAt(i - 1) != word2.charAt(j - 1)`，说明当前字符不同，此时有三种操作可选：
1. 替换：`dp[i - 1][j - 1] + 1` 2. 插入：`dp[i][j - 1] + 1` 3. 删除：`dp[i - 1][j] + 1` 取这三种操作的最小值，并加上对应的操作次数。
3. 结果：最终的最小编辑距离存储在 `dp[n1][n2]` 中，其中 `n1` 是 `word1` 的长度，`n2` 是 `word2` 的长度。
class Solution {
public int minDistance(String word1, String word2) {
int n1 = word1.length();
int n2 = word2.length();
// 为了处理第 0 行第 0 列空字符串的情况
int[][] dp = new int[n1 + 1][n2 + 1];
// 第一行
for (int j = 1; j <= n2; j++){
dp[0][j] = dp[0][j - 1] + 1;
}
// 第一列
for (int i = 1; i <= n1; i++) {
dp[i][0] = dp[i - 1][0] + 1;
}
for (int i = 1; i <= n1; i++) {
for (int j = 1; j <= n2; j++) {
if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
dp[i][j] = dp[i - 1][j - 1];
} else {
// 记得Math.min函数只接受两个参数，所以要放两个
dp[i][j] = Math.min(Math.min(dp[i - 1][j - 1], dp[i][j - 1]), dp[i - 1][j]) + 1;}
}
}
return dp[n1][n2];
}
}
最长公共子序列
1143. 最长公共子序列 - 力扣（LeetCode）
和 编辑距离 同为经典的双字符串动态规划问题。用两个指针 `i, j` 在两个字符串上游走，这就是「状态」，字符串中的每个字符都有两种「选择」，要么在 `lcs` 中，要么不在。
`dp[i][j]` 的含义是：对于 `s1[1..i]` 和 `s2[1..j]`，它们的 LCS 长度是 `dp[i][j]`
class Solution {
public int longestCommonSubsequence(String text1, String text2) {
int m = text1.length(), n = text2.length();
int[][] dp = new int[m + 1][n + 1];
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
// 实际上要从 0 开始， 所以要-1
if (text1.charAt(i - 1) == text2.charAt(j - 1)) {
// text1[i - 1] 和 text2[j - 1] 必然在lcs中
dp[i][j] = dp[i - 1][j - 1] + 1;
} else {
// text1[i - 1] 和 text2[j - 1] 至少有一个不在lcs中
dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
}
}
}
return dp[m][n];
}
}
相关文章
您阅读本篇文章共花了：
发表评论