Problem

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.

• 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:

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

    • if we added d after c:

      • 相应的理解:
        • 因为f[i][j-1]已经使word1[0...i-1]和word2[0...j-2]匹配好了, 那么word2[j-1]相对于word1就是缺少了的, 因此要插入(因为word1要按照word2来修改)
    • • f[i][j] = f[i][j-1] + 1;
    • if we deleted c and hence made word1[0..i - 2] = word2[0..j - 1] :
      • 相应的理解:
        • 因为f[i - 1][j]已经使word1[0...i-2]和word2[0...j-1]匹配好了, 那么word1[i-1]相对于word1就是多余的, 因此要删除 (因为word1是要被修改的那个)
      • f[i][j] = f[i-1][j] + 1;
    • 
    • 

    public int minDistance(String word1, String word2) {
        if (word1 == null || word2 == null) {
            return 0;
        }

        int l1 = word1.length();
        int l2 = word2.length();

        int[][] dp = new int[l1 + 1][l2 + 1];

        for (int i = 0; i <= l1; i++) {
            dp[i][0] = i;
        }
        for (int i = 0; i <= l2; i++) {
            dp[0][i] = i;
        }

        for (int i = 1; i <= l1; i++) {
            for (int j = 1; j <= l2; j++) {
                if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
                    if (i == j) {
                        dp[i][j] = dp[i - 1][j - 1];
                    } else {
                        dp[i][j] = dp[i - 1][j - 1];
                    }
                } else {
                    if (i == j) {
                        dp[i][j] = dp[i - 1][j - 1] + 1;
                    } else {
                        dp[i][j] = Math.min(dp[i][j - 1], dp[i - 1][j]) + 1;
                    }
                }
            }
        }

        return dp[l1][l2];
    }

滚动数组优化

    public int minDistance(String word1, String word2) {
        if (word1 == null || word2 == null) {
            return 0;
        }

        int l1 = word1.length();
        int l2 = word2.length();

        int[][] dp = new int[2][l2 + 1];

        for (int i = 0; i <= l2; i++) {
            dp[0][i] = i;
        }

        for (int i = 1; i <= l1; i++) {
            dp[i%2][0] = i;
            for (int j = 1; j <= l2; j++) {
                if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
                    dp[i%2][j] = dp[(i - 1)%2][j - 1];
                } else {
                    dp[i%2][j] = Math.min(dp[i%2][j - 1], dp[(i - 1)%2][j]) + 1;
                    dp[i%2][j] = Math.min(dp[(i - 1)%2][j - 1] + 1, dp[i%2][j]);
                }
            }
        }

        return dp[l1%2][l2];
    }