计算字符串的距离

这题考的是levenshtein距离的计算，需要运用动态规划去解决该类问题。

传递公式：

1. lev[i][j]用来表示字符串a的[1...i]和字符串b[1...j]的levenshtein距离；
2. 插入和删除操作互为逆过程：a删除指定字符变b等同于b插入指定字符变a；
3. 如果a[i] == b[j]，则说明a[i]和b[j]分别加入a，b之后不会影响levenshtein距离，lev[i][j] = lev[i-1][j-1] + 0;
4. 如果a[i] != b[j]，则需要考虑3种情况的可能：
   1. a中插入字符，即lev[i][j] = lev[i-1][j] + 1;
   2. b中插入字符，即lev[i][j] = lev[i][j-1] + 1;
   3. a[i]替换成b[j]，lev[i][j] = lev[i-1][j-1] + 1;
5. 取这4种情况的最小值。

题解

#include <iostream>
#include <cmath>
using namespace std;

int findMin(int a, int b, int c)
{
    a = min(a, b);
    b = min(b, c);
    return min(a, b);
}

int levenshtein(string a, string b)
{
    a.insert(0, 1,' ');
    b.insert(0, 1, ' ');
    int n = a.size(), m = b.size();
    int cost, lev[n][m];
    for(int i = 0; i < n; i++) lev[i][0] = i;
    for(int j = 0; j < m; j++) lev[0][j] = j;
    for(int i = 1; i < n; i++)
    {
        for(int j = 1; j < m; j++)
        {
            if(a[i] == b[j]) cost = 0;
            else cost = 1;
            lev[i][j] = findMin(lev[i][j-1]+1, 
                lev[i-1][j]+1, lev[i-1][j-1]+cost);
        }
    }
    return lev[n-1][m-1];
}

int main()
{
    string a, b;
    while(cin >> a >> b)
    {
        cout << levenshtein(a, b) << endl;
    }
    return 0;
}

https://github.com/ultraji/nowcoder