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:

a) Insert a character
b) Delete a character
c) Replace a character

Analysis

  • Classic DP problem
  • State: DP[i][j]: minimum number of steps convert word1[1:i] to word2[1:j] (here assume string start from 1)
  • Transfer function:
    • DP[i+1][j+1]= min of
      • DP[i][j]+1 or 0 (+0 if word1[i+1]==word2[j+1])
      • DP[i][j+1]+1
      • DP[i+1][j]+1
  • Initialization:
    • DP[0][j] = j: "" convert to word2[1:j]: j steps
    • DP[i][0] = i: word1[1:i] convert to "": i steps
    • DP[0][0] = 0: "" convert to "": 0 steps
  • Return: DP[word1.length][word2.length]

Analysis

Example: DP of "abc" transfer to "bccd"

0 1 2 3 4
"" b bc bcd bccd
0 "" 0 1 2 3 4
1 a 1 1 2 3 4
2 ab 2 1 2 3 4
3 abc 3 2 1 2 3

return 3

Code

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<word1.length()+1; i++){
            for (int j=0; j<word2.length()+1; j++){
                if (i==0) {dp[i][j]=j;}
                else if (j==0) {dp[i][j]=i;}
                else {
                    if (word1.charAt(i-1) == word2.charAt(j-1)) {dp[i][j]=dp[i-1][j-1];}
                    else {dp[i][j] = 1 + Math.min(Math.min(dp[i][j-1], dp[i-1][j]), dp[i-1][j-1]);}
                }
            }
        }

        return dp[word1.length()][word2.length()];

    }
}

Question

  • 为什么最后一个字母相同时直接等于dp i-1, j-1，如果不match最后一个字母有没有可能步数更少呢？

Reference

Yu