编辑距离

public class Solution {
    /*
    * 对于w1的第i位和w2的第j位，Dist(i,j)可能由三种情况转移而成：
    *   case1 ：Dist(i-1,j-1)，代表前i-1位和j-1位已经算好编辑距离，
    *       若w1[i]==w2[j]，则Dist(i,j)==Dist(i-1,j-1)；
    *       若w1[i]!=w2[j]，只需要把w1[i]替换成w2[j]，则Dist(i,j)==Dist(i-1,j-1)+1；
    *   case2 ：Dist(i-1,j)，代表前i-1位和j位已经算好编辑距离，
    *       只需要把w1[i]删除(因为w1的前i-1位和w2的前j位已经保证)，则Dist(i,j)==Dist(i-1,j)+1；
    *   case3 ：Dist(i,j-1)，代表前i位和j-1位已经算好编辑距离
    *       只需要w2[j]插入到w1的i位(因为w1的前i位和w2的前j-1位已经保证)，则Dist(i,j)==Dist(i,j-1)+1；
    *
    * 则有：minDist(i,j) = min(minDist(i-1,j-1)+(w1[i]==w2[j]?0:1), minDist(i,j-1)+1, minDist(i-1,j)+1);
    *
    * 当i=0, j=0，表示w1和w2都为"":
    *   minDist(0,0) = 0
    * 当i=1,2,3..., j=0，表示w2都为"":
    *   minDist(i,0) = i
    * 当i=0, j=1,2,3...，表示w1都为"":
    *   minDist(0,j) = j
    */
    public int minDistance (String word1, String word2) {

        int[][] recode = new int[word1.length()+1][word2.length()+1];
        for(int i=0; i<recode.length; i++) {
            for(int j=0; j<recode[0].length; j++) {
                if(i==0&&j>0) {
                    recode[i][j] = j;
                    continue;
                }
                if(i>0&&j==0) {
                    recode[i][j] = i;
                    continue;
                }
                if(i>0&&j>0) {
                    recode[i][j] = Math.min(Math.min(recode[i-1][j]+1, recode[i][j-1]+1),
                            recode[i-1][j-1]+(word1.charAt(i-1)==word2.charAt(j-1)?0:1));
                }

            }
        }
        return recode[word1.length()][word2.length()];
    }
}

public class Solution {
    public int minDistance(String word1, String word2) {
        int row = word1.length();
        int column = word2.length();
        int[][] distance = new int[row+1][column+1];
        for (int i = 0; i < column + 1; i++) distance[0][i] = i;
        for (int i = 0; i < row + 1; i++) distance[i][0] = i;
        for (int i = 1; i < row + 1; i++) {
            for (int j = 1; j < column + 1; j++) {
                if (word1.charAt(i-1) == word2.charAt(j-1)) {
                    distance[i][j] = distance[i-1][j-1];
                } else {
                    int temp = distance[i-1][j-1] < distance[i][j-1] ? distance[i-1][j-1] : distance[i][j-1];
                    int min = temp < distance[i-1][j] ? temp : distance[i-1][j];
                    distance[i][j] = min + 1;
                }
            }
        }
        return distance[row][column];
    }
}

Use f[i][j] to represent the shortest edit distance between word1[0,i) and word2[0, j). Then compare the last character of word1[0,i) and word2[0,j), which are c and d respectively (c == word1[i-1], d == word2[j-1]):

if c == d, then : f[i][j] = f[i-1][j-1]

Otherwise we can use three operations to convert word1 to word2:

(a) if we replaced c with d: f[i][j] = f[i-1][j-1] + 1;

(b) if we added d after c: f[i][j] = f[i][j-1] + 1;

(c) if we deleted c: f[i][j] = f[i-1][j] + 1;

Note that f[i][j] only depends on f[i-1][j-1], f[i-1][j] and f[i][j-1], therefore we can reduce the space to O(n) by using only the (i-1)th array and previous updated element(f[i][j-1]).

int minDistance(string word1, string word2) { int l1 = word1.size(); int l2 = word2.size(); vector<int> f(l2+1, 0); for (int j = 1; j <= l2; ++j)
            f[j] = j; for (int i = 1; i <= l1; ++i)
        { int prev = i; for (int j = 1; j <= l2; ++j)
            { int cur; if (word1[i-1] == word2[j-1]) {
                    cur = f[j-1];
                } else {
                    cur = min(min(f[j-1], prev), f[j]) + 1;
                }
    
                f[j-1] = prev;
                prev = cur;
            }
            f[l2] = prev;
        } return f[l2];
    
    }

Actually at first glance I thought this question was similar to Word Ladder and I tried to solve it using BFS(pretty stupid huh?). But in fact, the main difference is that there's a strict restriction on the intermediate words in Word Ladder problem, while there's no restriction in this problem. If we added some restriction on intermediate words for this question, I don't think this DP solution would still work.

public class Solution {
    public int minDistance(String word1, String word2) {
        int[][] dp = new int[word1.length() + 1][word2.length() + 1];
        for (int i = 0; i < dp[0].length; i ++ ) dp[0][i] = i;
        for (int i = 0; i < dp.length; i ++ ) dp[i][0] = i;
        for (int i = 1; i < dp.length; i ++ ) {
            for (int j = 1; j < dp[0].length; j ++ ) {
                if(word1.charAt(i - 1) == word2.charAt(j - 1)) dp[i][j] = dp[i - 1][j - 1];
                else dp[i][j] = Math.min(Math.min(dp[i - 1][j] + 1, dp[i][j - 1] + 1), dp[i - 1][j - 1] + 1);
            }
        }
        return dp[word1.length()][word2.length()];
    }
}