97. 交错字符串
给定三个字符串 s1、s2、s3，请你帮忙验证 s3 是否是由 s1 和 s2 交错 组成的。
两个字符串 s 和 t 交错 的定义与过程如下，其中每个字符串都会被分割成若干 非空
子字符串
：
s = s1 + s2 + ... + snt = t1 + t2 + ... + tm|n - m| <= 1- 交错 是
s1 + t1 + s2 + t2 + s3 + t3 + ...或者t1 + s1 + t2 + s2 + t3 + s3 + ...
注意：a + b 意味着字符串 a 和 b 连接。
示例 1：
输入：s1 = "aabcc", s2 = "dbbca", s3 = "aadbbcbcac"
输出：true示例 2：
输入：s1 = "aabcc", s2 = "dbbca", s3 = "aadbbbaccc"
输出：false示例 3：
输入：s1 = "", s2 = "", s3 = ""
输出：true提示：
0 <= s1.length, s2.length <= 1000 <= s3.length <= 200s1、s2、和s3都由小写英文字母组成
class Solution {
public boolean isInterleave(String s1, String s2, String s3) {
if (s1.length() + s2.length() != s3.length()) {
return false;
}
boolean[][] dp = new boolean[s1.length() + 1][s2.length() + 1];
dp[0][0] = true;
for (int i = 0; i <= s1.length(); i++) {
for (int j = 0; j <= s2.length(); j++) {
if (i > 0 && s1.charAt(i - 1) == s3.charAt(i + j - 1) && dp[i - 1][j]) {
dp[i][j] = true;
}
if (j > 0 && s2.charAt(j - 1) == s3.charAt(i + j - 1) && dp[i][j - 1]) {
dp[i][j] = true;
}
}
}
return dp[s1.length()][s2.length()];
}
}72. 编辑距离
给你两个单词 word1 和 word2， 请返回将 word1 转换成 word2 所使用的最少操作数
你可以对一个单词进行如下三种操作：
- 插入一个字符
- 删除一个字符
- 替换一个字符
示例 1：
输入：word1 = "horse", word2 = "ros"
输出：3
解释：
horse -> rorse (将 'h' 替换为 'r')
rorse -> rose (删除 'r')
rose -> ros (删除 'e')示例 2：
输入：word1 = "intention", word2 = "execution"
输出：5
解释：
intention -> inention (删除 't')
inention -> enention (将 'i' 替换为 'e')
enention -> exention (将 'n' 替换为 'x')
exention -> exection (将 'n' 替换为 'c')
exection -> execution (插入 'u')提示：
0 <= word1.length, word2.length <= 500word1和word2由小写英文字母组成
class Solution {
fun minDistance(word1: String, word2: String): Int {
val dp = IntArray(word2.length + 1) {
//当word1为空时需要增加word2的长度所以此处设为当前字符串的长度
it
}
//prev可理解为二维数组动态规划的dp[i - 1][j - 1]
var prev = 0
var current = 0
for (i in word1.indices) {
//边界条件，当j为0时，需要增加的字符串为当前下标的长度
prev = i
//边界条件，i为0时，需要增加的字符串为当前下标的长度+1
dp[0] = i + 1
for (j in 1..word2.length) {
//获取上一轮下标为j的值即dp[i - 1][j]
current = dp[j]
if (word1[i] == word2[j - 1]) {
dp[j] = minOf(minOf(dp[j], dp[j - 1]) + 1, prev)
} else {
dp[j] = minOf(minOf(dp[j], dp[j - 1]) + 1, prev + 1)
}
//赋值到prev，下次遍历的时候prev变成当前轮的j的前一个即dp[i - 1][j - 1]
prev = current
}
}
return dp[word2.length]
}
}
