题解 | 编辑距离

题干解析

题设给予我们两个字符串，我们每次能够对第一个字符串进行任意次以下操作之一：

• 删除一个字符
• 插入一个字符
• 更改一个字符 求将第一个字符串更改为第二个字符串的最少操作次数。

算法思路

设第一个字符串为s1，第二个为s2

我们定义二维状态数组dp[i][j]表示将s1的前i个字符字串更改为s2的前j个字符字串的最少操作次数。

不难得出如果针对s1[i]==s2[j]时，dp[i][j]=dp[i-1][j-1]，也就是说无需再进行操作，直接继承。

反之如果不成立，需要在原基础上进行一次操作：

• 删除一个字符操作：dp[i][j] = dp[i-1][j] + 1
• 插入一个字符操作：dp[i][j] = dp[i][j-1] + 1
• 更改一个字符操作：dp[i][j] = dp[i-1][j-1] + 1 三种操作取其总计操作数最小的一个即可。

由此状态转移方程如下：

实现代码

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    string s1, s2;
    cin >> s1 >> s2;
    vector<vector<int>> dp(s1.size() + 1, vector<int>(s2.size() + 1, 0));
    for (int i = 0; i <= s1.size(); ++i) {
        for (int j = 0; j <= s2.size(); ++j) {
            if (i > 0 && j > 0 && s1[i - 1] == s2[j - 1]) dp[i][j] = dp[i - 1][j - 1];
            else {
                if (!i && !j) continue;
                int min_ = INT_MAX;
                if (i > 0) min_ = min(min_, dp[i - 1][j]);
                if (j > 0) min_ = min(min_, dp[i][j - 1]);
                if (i > 0 && j > 0) min_ = min(min_, dp[i - 1][j - 1]);
                dp[i][j] = min_ + 1;
            }
        }
    }
    cout << dp[s1.size()][s2.size()];

    return 0;
}

复杂度分析

• 时间复杂度：，其中n为s1的长度，m为s2的长度，下同
• 空间复杂度：