题目
LeetCode.72.编辑距离（困难）
给你两个单词 word1 和 word2，请你计算出将 word1 转换成 word2 所使用的最少操作数 。
你可以对一个单词进行如下三种操作：
题解
看着题目就给出了原子化的最小操作步骤了，看着就能拆成子问题的样子。
从两个单词末尾开始看起。
- 如果
word1[i1] == word2[i2]，就不用操作；
接着就是去对比word1[0, i1 - 1]和word2[0, i2 - 1]这两个子字符串是不是一样，看子问题。
- 如果
word1[i1] != word2[i2]，那么每个单词都有三种操作可以变成另一个；
具体哪种操作后的总操作数最少呢？只能每个都试一下，然后选个操作数最少的。
状态转移方程
设dp[i][j]是word1[0, i]转换为word2[0, j]的操作数。
word1[i] == word2[j]时，
dp[i][j] = dp[i - 1][j - 1]word1[i] != word2[j]时：
word1末尾插入一个与word2[j]相同的字符，插入之前的操作数是dp[i][j - 1]。word1末尾删除一个字符，删除之前的操作数是dp[i - 1][j]。word1末尾字符替换为word2[j]，替换之前的操作数是dp[i - 1][j - 1]。- 取插入、删除、替换操作数中最小的一个，
dp[i][j] = 1 + minOf(dp[i][j - 1], dp[i - 1][j], dp[i - 1][j - 1])
边界条件
i == 0时，
dp[i - 1][j]表示空字符串变换到word2[0, j]需要的操作数，很显然要插入j + 1个字符，操作数是j + 1。dp[i - 1][j - 1]同理
j == 0时，
dp[i][j - 1]表示空字符串变换到word1[0, i]需要的操作数，很显然要插入i + 1个字符，操作数是i + 1。dp[i - 1][j - 1]同理
i == 0 && j == 0时，
dp[i - 1][j - 1]（即dp[-1][-1]）表时空字符串转换到空字符串，操作数为0。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| class Solution {
fun minDistance(word1: String, word2: String): Int {
fun min(i1: Int, i2: Int): Int {
if (i1 == -1) return i2 + 1
if (i2 == -1) return i1 + 1
return if (word1[i1] == word2[i2]) min(i1 - 1, i2 - 1)
else {
val insertion = min(i1, i2 - 1)
val deletion = min(i1 - 1, i2)
val replacement = min(i1 - 1, i2 - 1)
1 + minOf(insertion, deletion, replacement)
}
}
return min(word1.length - 1, word2.length - 1)
}
}
|
复杂度
设m为word1长度，n为word2长度，m < n。
画出递归树可以观察到，一个大问题最多可以拆解为3个子问题，也就是一个结点的下一层最多有3个结点，可以一直这样扩张，树高也就是m和n中的较大值。
最坏时间复杂度就是递归树的所有结点数，通过等比数列求和公式可得结点总数为 $O(3^n)$。
一次递归占用一个方法栈，空间复杂度就看同一时刻最多会有多少个方法栈存在，因为递归没有发现结果会回溯，所以得到正确答案的时候递归深度最深，也就是方法栈最多的时候。
空间复杂度 $O(n)$。
递归有大量重叠子问题，比如min(i1 - 1, i2 - 1)在依次经历过min(i1 - 1, i2)和min(i1 - 1, i2 - 1)后可以得到，计算了两次，后续递归还有更多重叠子问题，得把中间计算结果保存一下。
记忆化递归
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| class Solution {
fun minDistance(word1: String, word2: String): Int {
val n1 = word1.length
val n2 = word2.length
val memo = Array(n1) { IntArray(n2) { -1 } }
fun min(i1: Int, i2: Int): Int {
if (i1 == -1) return i2 + 1
if (i2 == -1) return i1 + 1
if (memo[i1][i2] != -1) return memo[i1][i2]
memo[i1][i2] = if (word1[i1] == word2[i2]) min(i1 - 1, i2 - 1)
else {
val insertion = min(i1, i2 - 1)
val deletion = min(i1 - 1, i2)
val replacement = min(i1 - 1, i2 - 1)
1 + minOf(insertion, deletion, replacement)
}
return memo[i1][i2]
}
return min(n1 - 1, n2 - 1)
}
}
|
自底向上递推
自底向上递推会用到前一项的值，为了避免大量边界判断，把dp数组长度加1。
dp[i][j]表示word1[0, i - 1]和word2[0, j - 1]的最小编辑距离。
dp[i][0]表示word1[0, i - 1]变成空字符串需要多少步操作，很显然是要删除word1[0,i - 1]所有字符，共有i个字符。
dp[0][j]表示空字符串要变成word2[0,j - 1]需要多少步操作，很显然是要插入word2[0, j - 1]全部字符，总共j个字符。
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 {
fun minDistance(word1: String, word2: String): Int {
val len1 = word1.length
val len2 = word2.length
val dp = Array(len1 + 1) { IntArray(len2 + 1) { 0 } }
for (i in 0..len1) {
dp[i][0] = i
}
for (i in 0..len2) {
dp[0][i] = i
}
for (i in 0 until len1) {
for (j in 0 until len2) {
if (word1[i] == word2[j]) {
dp[i + 1][j + 1] = dp[i][j]
} else {
val replacement = 1 + dp[i][j]
val insertion = 1 + dp[i + 1][j]
val deletion = 1 + dp[i][j + 1]
dp[i + 1][j + 1] = minOf(replacement, insertion, deletion)
}
}
}
return dp[len1][len2]
}
}
|
时间复杂度 ：O(mn)，m为word1长度，n为word2长度。
空间复杂度 ：O(mn)，需要用二维dp数组记录中间计算状态。
空间优化
dp[i][j]只跟左、上、左上三项有关，不需要用二维数组记录所有状态，只需要一行数组记录上一行状态即可。
这里有个问题在于，从左到右更新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
25
26
27
| class Solution {
fun minDistance(word1: String, word2: String): Int {
val len1 = word1.length
val len2 = word2.length
val dp = IntArray(len2 + 1) { 0 }
for (j in 0..len2) dp[j] = j
var pre = 0
for (i in 1..len1) {
pre = dp[0]
dp[0] = i
for (j in 1..len2) {
val tmp = dp[j]
if (word1[i - 1] == word2[j - 1]) dp[j] = pre
else {
val replacement = 1 + pre
val insertion = 1 + dp[j - 1]
val deletion = 1 + dp[j]
dp[j] = minOf(replacement, insertion, deletion)
}
pre = tmp
}
}
return dp[len2]
}
}
|
时间复杂度 ：O(mn)，m为word1长度，n为word2长度。
空间复杂度 ：O(n)，只需要用一维dp数组记录中间计算状态。