Edit Distance

题意是求俩字符串的编辑距离，编辑定义有三种1、插入字符 2、删除字符 3、替换字符。

int minDistance(string word1, string word2)
{
    if (word1.size() == 0) return (int)word2.size();
    if (word2.size() == 0) return (int)word1.size();

    int result = 0;
    int *dist = new int[(word1.size() + 1) * (word2.size() + 1)];

    for (size_t i = 0; i <= word1.size(); ++i)
    {
        dist[i] = (int)i;
    }

    for (size_t j = 0; j <= word2.size(); ++j)
    {
        dist[j * word1.size()] = (int)j;
    }

    for (size_t i = 1; i <= word1.size(); ++i)
    {
        for (size_t j = 1; j <= word2.size(); ++j)
        {
            if (word1[i - 1] == word2[j - 1])
            {
                // dist[i, j] = dist[i - 1, j - 1]
                dist[j * word1.size() + i] =
                        dist[(j - 1) * word1.size() + i - 1];
            }
            else
            {
                // minDist = min(dist[i - 1, j], dist[i, j - 1])
                const int minDist = min(
                        dist[j * word1.size() + (i - 1)],
                        dist[(j - 1) * word1.size() + i]);

                // dist[i, j] = min(minDist, dist[i - 1, j - 1]) + 1
                dist[j * word1.size() + i] = min(minDist,
                        dist[(j - 1) * word1.size() + i - 1]) + 1;
            }
        }
    }

    result = dist[word2.size() * word1.size() + word1.size()];

    delete[] dist;

    return result;
}