题解 | 计算字符串的编辑距离

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

int main() {
    string s, t;
    cin >> s >> t;
    int n = s.size(), m = t.size();

    // 只开一行滚动数组，空间 O(m)
    vector<int> prev(m + 1), cur(m + 1);
    for (int j = 0; j <= m; ++j) prev[j] = j;   // s 为空时，需要 j 次插入

    for (int i = 1; i <= n; ++i) {
        cur[0] = i;                             // t 为空时，需要 i 次删除
        for (int j = 1; j <= m; ++j) {
            int cost = (s[i - 1] == t[j - 1]) ? 0 : 1;
            cur[j] = min({
                prev[j] + 1,            // 删除 s[i-1]
                cur[j - 1] + 1,         // 在 s 里插入 t[j-1]
                prev[j - 1] + cost      // 替换/匹配 s[i-1] -> t[j-1]
            });
        }
        swap(prev, cur);
    }
    cout << prev[m] << '\n';
    return 0;
}