字符串编辑距离

Edit Distance （https://leetcode.com/problems/edit-distance/）

Given two words word1 and word2, find the minimum number of operations required to convert word1 to word2.

You have the following 3 operations permitted on a word:

1. Insert a character
2. Delete a character
3. Replace a character

以下转载Leetcode上大神的做法：
To apply DP, we define the state dp[i][j] to be the minimum number of operations to convert word1[0..i) to word2[0..j).

For the base case, that is, to convert a string to an empty string, the mininum number of operations (deletions) is just the length of the string. So we have dp[i][0] = i and dp[0][j] = j.

For the general case to convert word1[0..i) to word2[0..j), we break this problem down into sub-problems. Suppose we have already known how to convert word1[0..i - 1) to word2[0..j - 1) (dp[i - 1][j - 1]), if word1[i - 1] == word2[j - 1], then no more operation is needed and dp[i][j] = dp[i - 1][j - 1].

If word1[i - 1] != word2[j - 1], we need to consider three cases.

Replace word1[i - 1] by word2[i - 1] #dp[i][j] = dp[i - 1][j - 1] + 1#;
If word1[0..i - 1) = word2[0..j) then delete word1[i - 1] (dp[i][j] = dp[i - 1][j] + 1);
If word1[0..i) + word2[j - 1] = word2[0..j) then insert word2[j - 1] to word1[0..i) (dp[i][j] = dp[i][j - 1] + 1).
So when word1[i - 1] != word2[j - 1], dp[i][j] will just be the minimum of the above three cases.

int minDistance(string word1, string word2) {
        int m = word1.size();
        int n = word2.size();
        vector<int> dp(n+1,0);
        for (int k = 1;k<=n;k++) dp[k]=k;

        int pre;
        for (int i = 1;i<=m;i++){
            pre = dp[0];
            dp[0] = i;
            for (int j =1;j<=n;j++){
                int tmp = dp[j];
                if (word1[i-1] == word2[j-1]){
                    dp[j] = pre;
                }
                else{

                    dp[j] = min(pre, min(dp[j-1], dp[j]))+1;
                }
                pre = tmp;
            }
        }
        return dp[n];