题目链接 · 灵神原题解（署名来源）

视频讲解

请看【基础算法精讲 19】。如果这个视频对你有帮助，欢迎点赞关注！

答疑

问：为什么只需考虑从右往左（或者从左往右）操作？我就不能从中间开始操作吗？

答：假设两个字符为 $s[i]$ 和 $t[j]$，先操作 $i$ 再操作 $j$，还是先操作 $j$ 再操作 $i$，结果都是一样的。推广，任意一种操作顺序，都可以重新排列成从右往左（从左往右）操作。

一、递归搜索 + 保存计算结果 = 记忆化搜索

Python 解法1

class Solution:
    def minDistance(self, s: str, t: str) -> int:
        n, m = len(s), len(t)
        @cache  # 缓存装饰器，避免重复计算 dfs 的结果（记忆化）
        def dfs(i: int, j: int) -> int:
            if i < 0:
                return j + 1
            if j < 0:
                return i + 1
            if s[i] == t[j]:
                return dfs(i - 1, j - 1)
            return min(dfs(i - 1, j), dfs(i, j - 1), dfs(i - 1, j - 1)) + 1
        return dfs(n - 1, m - 1)

C++ 解法1

// C++ 版待补充

C++ 解法2

class Solution {
public:
    int minDistance(string s, string t) {
        int n = s.length(), m = t.length();
        vector memo(n, vector<int>(m, -1)); // -1 表示还没有计算过
        auto dfs = [&](this auto&& dfs, int i, int j) -> int {
            if (i < 0) {
                return j + 1;
            }
            if (j < 0) {
                return i + 1;
            }
            int& res = memo[i][j]; // 注意这里是引用
            if (res != -1) {
                return res; // 之前算过了
            }
            if (s[i] == t[j]) {
                return res = dfs(i - 1, j - 1);
            }
            return res = min({dfs(i - 1, j), dfs(i, j - 1), dfs(i - 1, j - 1)}) + 1;
        };
        return dfs(n - 1, m - 1);
    }
};

复杂度分析

• 时间复杂度：$\mathcal{O}(nm)$，其中 $n$ 为 $s$ 的长度，$m$ 为 $t$ 的长度。
• 空间复杂度：$\mathcal{O}(nm)$。

二、1:1 翻译成递推

Python 解法3

class Solution:
    def minDistance(self, s: str, t: str) -> int:
        n, m = len(s), len(t)
        f = [[0] * (m + 1) for _ in range(n + 1)]
        f[0] = list(range(m + 1))
        for i, x in enumerate(s):
            f[i + 1][0] = i + 1
            for j, y in enumerate(t):
                f[i + 1][j + 1] = f[i][j] if x == y else \
                        min(f[i][j + 1], f[i + 1][j], f[i][j]) + 1
        return f[n][m]

C++ 解法3

// C++ 版待补充

C++ 解法4

class Solution {
public:
    int minDistance(string s, string t) {
        int n = s.length(), m = t.length();
        vector f(n + 1, vector<int>(m + 1));
        for (int j = 0; j < m; j++) {
            f[0][j + 1] = j + 1;
        }
        for (int i = 0; i < n; i++) {
            f[i + 1][0] = i + 1;
            for (int j = 0; j < m; j++) {
                f[i + 1][j + 1] = s[i] == t[j] ? f[i][j] :
                        min({f[i][j + 1], f[i + 1][j], f[i][j]}) + 1;
            }
        }
        return f[n][m];
    }
};

复杂度分析

• 时间复杂度：$\mathcal{O}(nm)$，其中 $n$ 为 $s$ 的长度，$m$ 为 $t$ 的长度。
• 空间复杂度：$\mathcal{O}(nm)$。

三、空间优化：两个数组（滚动数组）

Python 解法5

class Solution:
    def minDistance(self, s: str, t: str) -> int:
        n, m = len(s), len(t)
        f = [list(range(m + 1)), [0] * (m + 1)]
        for i, x in enumerate(s):
            f[(i + 1) % 2][0] = i + 1
            for j, y in enumerate(t):
                f[(i + 1) % 2][j + 1] = f[i % 2][j] if x == y else \
                        min(f[i % 2][j + 1], f[(i + 1) % 2][j], f[i % 2][j]) + 1
        return f[n % 2][m]

C++ 解法5

// C++ 版待补充

C++ 解法6

class Solution {
public:
    int minDistance(string s, string t) {
        int n = s.length(), m = t.length();
        vector f(2, vector<int>(m + 1));
        for (int j = 0; j < m; j++) {
            f[0][j + 1] = j + 1;
        }
        for (int i = 0; i < n; i++) {
            f[(i + 1) % 2][0] = i + 1;
            for (int j = 0; j < m; j++) {
                f[(i + 1) % 2][j + 1] = s[i] == t[j] ? f[i % 2][j] :
                        min({f[i % 2][j + 1], f[(i + 1) % 2][j], f[i % 2][j]}) + 1;
            }
        }
        return f[n % 2][m];
    }
};

复杂度分析

• 时间复杂度：$\mathcal{O}(nm)$，其中 $n$ 为 $s$ 的长度，$m$ 为 $t$ 的长度。
• 空间复杂度：$\mathcal{O}(m)$。

四、空间优化：一个数组

Python 解法7

class Solution:
    def minDistance(self, s: str, t: str) -> int:
        f = list(range(len(t) + 1))
        for x in s:
            pre = f[0]
            f[0] += 1  # f[0] = i + 1
            for j, y in enumerate(t):
                tmp = f[j + 1]
                f[j + 1] = pre if x == y else min(f[j + 1], f[j], pre) + 1
                pre = tmp
        return f[-1]

C++ 解法7

// C++ 版待补充

C++ 解法8

class Solution {
public:
    int minDistance(string s, string t) {
        int m = t.length();
        vector<int> f(m + 1);
        for (int j = 0; j < m; j++) {
            f[j + 1] = j + 1;
        }
        for (char x : s) {
            int pre = f[0];
            f[0]++; // f[0] = i + 1
            for (int j = 0; j < m; j++) {
                int tmp = f[j + 1];
                f[j + 1] = x == t[j] ? pre : min({f[j + 1], f[j], pre}) + 1;
                pre = tmp;
            }
        }
        return f[m];
    }
};

复杂度分析

• 时间复杂度：$\mathcal{O}(nm)$，其中 $n$ 为 $s$ 的长度，$m$ 为 $t$ 的长度。
• 空间复杂度：$\mathcal{O}(m)$。

专题训练

见下面动态规划题单的「§4.1 最长公共子序列（LCS）」。

分类题单

如何科学刷题？

1. 滑动窗口与双指针（定长/不定长/单序列/双序列/三指针/分组循环）
2. 二分算法（二分答案/最小化最大值/最大化最小值/第K小）
3. 单调栈（基础/矩形面积/贡献法/最小字典序）
4. 网格图（DFS/BFS/综合应用）
5. 位运算（基础/性质/拆位/试填/恒等式/思维）
6. 图论算法（DFS/BFS/拓扑排序/基环树/最短路/最小生成树/网络流）
7. 动态规划（入门/背包/划分/状态机/区间/状压/数位/数据结构优化/树形/博弈/概率期望）
8. 常用数据结构（前缀和/差分/栈/队列/堆/字典树/并查集/树状数组/线段树）
9. 数学算法（数论/组合/概率期望/博弈/计算几何/随机算法）
10. 贪心与思维（基本贪心策略/反悔/区间/字典序/数学/思维/脑筋急转弯/构造）
11. 链表、二叉树与回溯（前后指针/快慢指针/DFS/BFS/直径/LCA/一般树）
12. 字符串（KMP/Z函数/Manacher/字符串哈希/AC自动机/后缀数组/子序列自动机）

我的题解精选（已分类）

欢迎关注 B站@灵茶山艾府