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] 表示插入操作。
注意,针对第一行,第一列要单独考虑,我们引入 ‘’ 下图所示:
class Solution {
public int minDistance(String word1, String word2) {
int n1 = word1.length();
int n2 = word2.length();
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 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];
}
}
97. 交错字符串
思路:类似于编辑距离
能往下延伸的条件是: [i-1][j] = true 且 s1当前位置的字符和[i+j-1]的字符相同 或者 [i][j-1] = true 且 s2当前位置的字符和[i+j-1]的字符相同 状态方程:
边界 1:dp[0][0] = true; 边界 2:if i=0 : dp[0]dp[j] = s2[0-j) equals s3[0,j) 遇到 false 后面可以直接省略 边界 3:if j=0 : dp[i]dp[0] = s1[0-i) equals s3[0,i) 遇到 false 后面可以直接省略
class Solution {
public boolean isInterleave(String s1, String s2, String s3) {
int n1 = s1.length();
int n2 = s2.length();
int n3 = s3.length();
if (n1 + n2 != n3) {
return false;
}
boolean[][] dp = new boolean[n1 + 1][n2 + 1];
for (int i = 1; i <= n1 && s1.charAt(i-1) == s3.charAt(i-1); i++) dp[i][0] = true; // 不相符直接终止
for (int j = 1; j <= n2 && s2.charAt(j-1) == s3.charAt(j-1); j++) dp[0][j] = true; // 不相符直接终止
dp[0][0] = true;
for (int i = 1; i < n1 + 1; i++) {
for (int j = 1; j < n2 + 1; j++) {
dp[i][j] = (dp[i - 1][j] && s1.charAt(i - 1) == s3.charAt(i + j - 1))
|| (dp[i][j - 1] && s2.charAt(j - 1) == s3.charAt(i + j - 1));
}
}
return dp[n1][n2];
}
}