Given two strings of alphanumeric characters, determine the minimum number ofReplace,Delete, andInsertoperations needed to transform one string into the other.

Assumptions

• Both strings are not null

Examples

string one: “sigh”, string two : “asith”

the edit distance between one and two is 2 (one insert “a” at front then replace “g” with “t”).

Solution: dp[i][j]: s的前i个字母最小经过几次edit可变为t的前j个字母

           dp\[i - 1\]\[j - 1\], if s.charAt\(i - 1\) == t.charAt\(j - 1\)        case 1a: do nothing

           dp\[i - 1\]\[j - 1\] + 1, if s.charAt\(i - 1\) != t.charAt\(j - 1\)   case 1b: replace

dp[i][j] = dp[i][j - 1] + 1 case 2: add a letter to s

            dp\[i - 1\]\[j\] + 1                                        case 3: delete a letter from s

求min

  public int editDistance(String one, String two) {
    int m = one.length(), n = two.length();
    int[][] dp = new int[m + 1][n + 1];
    for (int i = 0; i <= m; i++) {
      dp[i][0] = i;
    }
    for (int i = 0; i <= n; i++) {
      dp[0][i] = i;
    }
    for (int i = 1; i <= m; i++) {
      for (int j = 1; j <= n; j++) {
        if (one.charAt(i - 1) == two.charAt(j - 1)) {
          dp[i][j] = dp[i - 1][j - 1];
        } else {
          dp[i][j] = dp[i - 1][j - 1] + 1;
        }
        dp[i][j] = Math.min(Math.min(dp[i - 1][j] + 1, dp[i][j - 1] + 1), dp[i][j]);
      }
    }
    return dp[m][n];
  }