BiruLyu
8/2/2017 - 5:40 AM

72. Edit Distance(#).java

public class Solution {
public int minDistance(String word1, String word2) {
if(word1 == null || word1.isEmpty()) return word2.length();
if(word2 == null || word2.isEmpty()) return word1.length();
char [] str1 = word1.toCharArray();
char [] str2 = word2.toCharArray();
int l1 = word1.length(), l2 = word2.length(), count = 0;
int [][] mem = new int[l1][l2];
/*for(int i = 1 ; i < l1 + 1 ; i++){
for(int j = 1 ; j < l2 + 1 ; j++){
if(str1[i-1] != str2[j-1]){
count += (min(mem[i-1][j-1], mem[i-1][j], mem[i][j-1])) + 1;
}
}
}
return count;*/
for(int[] row: mem) Arrays.fill(row, -1);
return minDistance(str1, str2, 0, 0, mem);
}
private int minDistance(char[] str1, char[] str2, int i, int j, int[][] mem)
{
if(i == str1.length) return str2.length - j;
if(j == str2.length) return str1.length - i;
if(mem[i][j] != -1) return mem[i][j];
if(str1[i] == str2[j])
{
mem[i][j] = minDistance(str1, str2, i+1, j+1, mem);
return mem[i][j];
}
else
{
mem[i][j] = 1 + min(minDistance(str1, str2, i+1, j, mem),
minDistance(str1, str2, i, j+1, mem),
minDistance(str1, str2, i+1, j+1, mem));
return mem[i][j];
}
}

private int min(int a, int b, int c){
int t = b < c ? b : c;
return a < t ? a : t;
}
}
/*
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]).
*/
public class Solution {
public int minDistance(String word1, String word2) {
int m = word1.length();
int n = word2.length();

int[][] cost = new int[m + 1][n + 1];
for(int i = 0; i <= m; i++)
cost[i][0] = i;
for(int i = 1; i <= n; i++)
cost[0][i] = i;

for(int i = 1; i <= m; i++) {
for(int j = 1; j <= n; j++) {
if(word1.charAt(i - 1) == word2.charAt(j - 1))
cost[i][j] = cost[i - 1][j - 1];
else {
int a = cost[i - 1][j - 1];
int b = cost[i - 1][j];
int c = cost[i][j - 1];
cost[i][j] = a < b ? (a < c ? a : c) : (b < c ? b : c);
cost[i][j]++;
}
}
}
return cost[m][n];
}
}