Edit Distance

Given two strings of alphanumeric characters, determine the minimum number of Replace, Delete, and Insert operations 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

public class Solution {
  public int editDistance(String one, String two) {

    //Each Square three cases:
    //Add or delete from top or left
    //replace or keep from left up diagonal

    if (one.length() == 0) return two.length();
    if (two.length() == 0) return one.length();

    int rows = one.length() + 1;
    int cols = two.length() + 1;

    int[][] M = new int[rows][cols];

    for (int i = 0; i < rows; i++) {
      M[i][0] = i;
    }

    for (int j = 0; j < cols; j++) {
      M[0][j] = j;
    }

    for (int i = 1; i < rows; i++){
      for (int j = 1; j < cols; j++){
        int top = M[i - 1][j];
        int left = M[i][j - 1];
        int diag = M[i - 1][j - 1];

        if (one.charAt(i - 1) == two.charAt(j - 1)){
          M[i][j] = diag;
        } else {
          M[i][j] = Math.min(Math.min(top, left), diag) + 1;
        }
      }
    }

    return M[rows - 1][cols - 1];
  }

}

TC: O(M*N) double for loop

SC: O(M*N) int[][] size