Given two words word1 and word2, find the minimum number of steps required to convert word1 to word2. (each operation is counted as 1 step.) You have the following 3 operations permitted on a word: a) Insert a character b) Delete a character c) Replace a character http://leetcode.com/onlinejudge

leetcode_edit_distance.cpp

class Solution {
public:
    int minDistance(string word1, string word2) {
        int n = word1.size();
        int m = word2.size();
        if (n == 0 || m == 0)
            return max(n, m);
        int **f = new int*[n];
        for (int i = 0; i < n; ++i)
            f[i] = new int[m];
        int max_ = max(n, m);
        for (int i = 0; i < n; ++i)
            for (int j = 0; j < m; ++j) {
                if (i == 0 || j == 0) {
                    if (i == 0 && j == 0)
                        f[i][j] = (word1[0] == word2[0] ? 0 : 1);
                    else if (i == 0)
                        f[i][j] = (word1[0] == word2[j] ? j : f[0][j - 1] + 1);
                    else
                        f[i][j] = (word1[i] == word2[0] ? i : f[i - 1][0] + 1);
                    continue;
                }
                f[i][j] = max_;
                if (word1[i] == word2[j]) {
                    f[i][j] = min(f[i][j], f[i - 1][j - 1]);
                }
                else {
                    f[i][j] = min(f[i][j], f[i][j - 1] + 1);
                    f[i][j] = min(f[i][j], f[i - 1][j] + 1);
                    f[i][j] = min(f[i][j], f[i - 1][j - 1] + 1);
                }
            }
        int ret = f[n - 1][m - 1];
        for (int i = 0; i < n; ++i)
            delete[] f[i];
        delete[] f;
        return ret;
    }
};