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

#include <iostream>

using namespace std;

int dp[1001][1001];

/**
 * Levenshtein 距离，又称编辑距离，指的是两个字符串之间，由一个转换成另一个所需的最少编辑操作次数。
 * 将一个字符替换成另一个字符，插入一个字符，删除一个字符
 * dp[i][j]表示word1第i-1字节为末尾子串和word2第j-1字节为末尾子串的最小编辑距离
 */
int Levenshtein(string word1, string word2) {
    for (int i = 0; i <= word1.size(); ++i) {
        dp[i][0] = i;
    }
    for (int j = 0; j <= word2.size(); ++j) {
        dp[0][j] = j;
    }

    for (int i = 1; i <= word1.size(); ++i) {
        for (int j = 1; j <= word2.size(); ++j) {
            if (word1[i-1] == word2[j-1]) {
                dp[i][j] = dp[i - 1][j - 1];
            } else {
                dp[i][j] = min(dp[i - 1][j] + 1, dp[i][j - 1] + 1);
                dp[i][j] = min(dp[i][j], dp[i - 1][j - 1] + 1);
            }
        }
    }
    return dp[word1.size()][word2.size()];
}

int main() {
    string str1, str2;
    while (cin >> str1 >> str2) {
        cout << Levenshtein(str1, str2) << endl;
    }
    return 0;
}