Edit Distance

题目：

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:

Insert a character; Delete a character; Replace a character.

Example: Given word1 = "mart" and word2 = "karma", return 3.

分析：

这种双序列的题目有个典型的情况，给两个序列，新进来一个A[next]一个B[next]。如果A[next] == B[next]怎么怎么样，如果A[next] != B[next]又怎么怎么样。把function填写好，就妥帖了。

解法：

class Solution {
public:    
    /**
     * @param word1 & word2: Two string.
     * @return: The minimum number of steps.
     */
    int minDistance(string word1, string word2) {
        // write your code here
        int m = word1.size();
        int n = word2.size();
        if (m == 0) {
            return n;
        }
        if (n == 0) {
            return m;
        }

        vector<vector<int> > f(m + 1, vector<int>(n + 1, INT_MAX) );
        for (int i = 0; i <= m; i++) {
            f[i][0] = i;
        }
        for (int j = 0; j <= n; j++) {
            f[0][j] = j;
        }

        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (word1[i - 1] == word2[j - 1]) {
                    f[i][j] = f[i - 1][j - 1];
                } else {
                    f[i][j] = min(min(f[i - 1][j], f[i][j - 1]), f[i - 1][j - 1]) + 1;
                }
            }
        }

        return f[m][n];
    }
};