思路

一直都不知道类似计算两个字符串的“距离”的题目怎么写，于是就有了这篇文章，先看一个经典的编辑距离。

题目给出两个字符串，并且可以对它们进行增加、修改、插入一个字符的操作，求最少的使两个字符串相等的操作步数$s$。

从后往前看，假设两个字符串是word1 = 'abcd'、word2 = 'abcc'，当前下标分别是$i$、$j$，每一步遍历都有 4 个可能的分支：

1. 末尾字符不相等，word1[i] != word2[j]：
   1.1. 可以把word1[i]替换为word2[j]，然后$i$、$j$各前移一位，操作步数$s$ + 1；
   1.2. 删掉word1[i]，然后$i$前移一位，操作步数$s$ + 1。其实这和从头到尾遍历到$i-1$、$j$时，word1增加一个word2[j]一样；
   1.3. 删掉word2[j]，然后$j$前移一位，操作步数$s$ + 1；
2. 末尾字符相等，则$i$、$j$各前移一位，，操作步数$s$不变。

记忆化搜索

于是就有了递归式的代码，这里方便起见把空字符''记为单词第一个元素。

此外，这里加上记忆化搜索，因为暴力递归的话，会使得代码时间复杂度达到$O(2^{mn})$，$m$、$n$是字符串长度，记忆化搜索时间、空间复杂度都为$O(mn)$。

ts
function minDistance(word1: string, word2: string): number {
    let len1 = word1.length
    let len2 = word2.length
    if (len1 ===0 || len2 === 0) {
        return len1 + len2
    }
    const cache = []
    for (let i = 0; i <= len1; i++) {
        cache[i] = new Array(len2 + 1).fill(-1)
    }
    const dfs = (i: number, j: number): number => {
        if (cache[i][j] >= 0) {
            return cache[i][j]
        }
        let ans
        if (i === 0 || j === 0) {
            ans = i || j
        } else if (word1[i - 1] !== word2[j - 1]) {
            ans = Math.min(
                dfs(i - 1, j),
                dfs(i, j - 1),
                dfs(i - 1, j - 1)
            ) + 1
        } else {
            ans = dfs(i - 1, j - 1)
        }
        return cache[i][j] = ans
    }
    return dfs(len1, len2)
}

递推式动态规划

类似的，我们可以使用递推式，从上面的思路可知，递推式的初始状态是，下标都指向单词的第一项空字符时，此时这个字符相等，只需要操作需要 0 步。当其中一个下标指向空字符，当前操作步数为$\text{abs}(i-j)$。

另外，这里进行了状态压缩，用两行的数组代替了所需的$m \times n$的数组，时间复杂度$O(mn)$，空间复杂度$O(\min(m,n))$。

ts
function minDistance(word1: string, word2: string): number {
    let len1 = word1.length
    let len2 = word2.length
    if (len1 === 0 || len2 === 0){
        return len1 + len2
    }
    if (len1 < len2) {
        return minDistance(word2, word1)
    }
    const dp: [number[], number[]] =[[], []]
    for (let j = 0; j < len2 + 1; j++) {
        dp[0][j] = j;
    }
    for (let i = 1; i < len1 + 1; i++) {
        for (let j = 0; j < len2 + 1; j++) {
            dp[1][j] = j === 0
                ? i
                : word1[i - 1] !== word2[j - 1]
                    ? Math.min(
                        dp[0][j - 1],
                        dp[0][j],
                        dp[1][j - 1]
                    ) + 1
                    : dp[0][j - 1]
        }
        [dp[0], dp[1]] = [dp[1], dp[0]]
    }
    return dp[0][len2]
}