编辑距离

GitHub跳转原题关系图返回列表

二维 DP：插入、删除、替换分别对应三个相邻状态转移，取最小值。

OJ: leetcodecn

题目 ID: edit-distance

难度:提高+/省选-

标签:动态规划字符串

日期: 2026-07-29 12:58

目录

  1. 题意
  2. 思路
  3. 代码
  4. 复杂度
  5. 总结

题意

求两个字符串之间的最小编辑距离（插入、删除、替换）。

思路

dp[i][j] 表示 word1[0..i-1] 变成 word2[0..j-1] 的最少操作数。若 word1[i-1] == word2[j-1]，则 dp[i][j] = dp[i-1][j-1]；否则 dp[i][j] = 1 + min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1])，分别对应删除、插入、替换。

代码

cpp
#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    int minDistance(string a, string b) {
        int m = a.size(), n = b.size();
        vector<int> dp(n + 1);
        iota(dp.begin(), dp.end(), 0);
        for (int i = 1; i <= m; i++) {
            int prev = dp[0];
            dp[0] = i;
            for (int j = 1; j <= n; j++) {
                int tmp = dp[j];
                if (a[i - 1] == b[j - 1])
                    dp[j] = prev;
                else
                    dp[j] = 1 + min({dp[j], dp[j - 1], prev});
                prev = tmp;
            }
        }
        return dp[n];
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    string a, b;
    cin >> a >> b;
    cout << Solution().minDistance(a, b) << '\n';
    return 0;
}
python
#!/usr/bin/env python3
class Solution:
    def minDistance(self, word1: str, word2: str) -> int:
        m, n = len(word1), len(word2)
        dp = list(range(n + 1))
        for i in range(1, m + 1):
            prev = dp[0]
            dp[0] = i
            for j in range(1, n + 1):
                tmp = dp[j]
                if word1[i - 1] == word2[j - 1]:
                    dp[j] = prev
                else:
                    dp[j] = 1 + min(dp[j], dp[j - 1], prev)
                prev = tmp
        return dp[n]


def main():
    a = input().strip()
    b = input().strip()
    print(Solution().minDistance(a, b))


if __name__ == "__main__":
    main()

复杂度

  • 时间复杂度：O(mn)O(mn)。
  • 空间复杂度：O(mn)O(mn)。

总结

编辑距离的三个操作对应三个相邻状态：删除从 dp[i-1][j] 转移，插入从 dp[i][j-1] 转移，替换从 dp[i-1][j-1] 转移。