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

#include <string>
#include <algorithm>
#include <iostream>
using namespace std;
int minDistance(const string& word1, const string& word2) {
    int n = word1.length();
    int m = word2.length();

// 有一个字符串为空串
    if (n * m == 0) return n + m;

// DP 数组
    int D[n + 1][m + 1];

// 边界状态初始化
    for (int i = 0; i < n + 1; i++) {
        D[i][0] = i;
    }
    for (int j = 0; j < m + 1; j++) {
        D[0][j] = j;
    }

// 计算所有 DP 值
    for (int i = 1; i < n + 1; i++) {
        for (int j = 1; j < m + 1; j++) {
            int left = D[i - 1][j] + 1;
            int down = D[i][j - 1] + 1;
            int left_down = D[i - 1][j - 1];
            if (word1[i - 1] != word2[j - 1]) left_down += 1;
            D[i][j] = min(left, min(down, left_down));
        }
    }
    return D[n][m];
}
int main() {
    string sA, sB;
    while (cin >> sA >> sB) {
        cout << minDistance(sA, sB) << endl;
    }
}