Edit Distance Problem

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

/**
     * For each poisition, check three subproblem:
     * 1. insert
     * 2. delete
     * 3. replace
     * We only modify the first string since no matter which one we choose, the result is the same. 
     * Need to optimize it using cache, which is the idea of dynamic programming. 
     * The key point is to find out the subproblem we have solved duplicately and cache the recursion.
     * Noticed that each subproblem is specificed by i and j pointer, so we can cache the result of these subproblems. 
     */
public int minDistance(String word1, String word2) {
	if (word1 == null || word1.length() == 0) return word2.length();
	if (word2 == null || word2.length() == 0) return word1.length();
	
	return match(word1, word2, 0, 0);
}

private int match(String s1, String s2, int i, int j) {
	//If one of the string's pointer have reached the end of it
	if (s1.length() == i) {
		return s2.length() - j;
	}
	if (s2.length() == j) {
		return s1.length() - i;
	}
	
	int res;
	//If current poisition is the same.
	if (s1.charAt(i) == s2.charAt(j)) {
		res = match(s1, s2, i + 1, j + 1);
	} else {
		//Case1: insert
		int insert = match(s1, s2, i, j + 1);
		//Case2: delete
		int delete = match(s1, s2, i + 1, j);
		//Case3: replace
		int replace = match(s1, s2, i + 1, j + 1);
		res = Math.min(Math.min(insert, delete), replace) + 1;
	}
	
	return res;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

public int minDistance(String word1, String word2) {
	if (word1 == null || word2 == null) return -1;
	if (word1.length() == 0) return word2.length();
	if (word2.length() == 0) return word1.length();
	
	char[] c1 = word1.toCharArray();
	char[] c2 = word2.toCharArray();
	
	int[][] cache = new int[c1.length][c2.length];
	for (int i = 0; i < c1.length; i++) {
		for (int j = 0; j < c2.length; j++) {
			cache[i][j] = -1;
		}
	}
	
	return match(c1, c2, 0, 0, cache);
}

private int match(char[] c1, char[] c2, int i, int j, int[][] cache) {
	if (c1.length == i) return c2.length - j;
	if (c2.length == j) return c1.length - i;
	
	if (cache[i][j] != -1) {
		return cache[i][j];
	}
	
	if (c1[i] == c2[j]) {
		cache[i][j] = match(c1, c2, i + 1, j + 1, cache);
	} else {
		//Case1: insert
		int insert = match(c1, c2, i, j + 1, cache);
		//Case2: delete
		int delete = match(c1, c2, i + 1, j, cache);
		//Case3: replace
		int replace = match(c1, c2, i + 1, j + 1, cache);
		
		cache[i][j] = Math.min(Math.min(insert, delete), replace) + 1;
	}
	
	return cache[i][j];
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

public int minDistance(String word1, String word2) {
	if (word1 == null || word2 == null) return -1;
	if (word1.length() == 0) return word2.length();
	if (word2.length() == 0) return word1.length();
	
	char[] c1 = word1.toCharArray();
	char[] c2 = word2.toCharArray();
	
	int[][] matched = new int[c1.length + 1][c2.length + 1];
	//matched[length of c1 already been matched][length of c2 already been matched]
	
	for (int i = 0; i <= c1.length; i++) {
		matched[i][0] = i;
	}
	for (int j = 0; j <= c2.length; j++) {
		matched[0][j] = j;
	}
	
	for (int i = 0; i < c1.length; i++) {
		for (int j = 0; j < c2.length; j++) {
			if (c1[i] == c2[j]) {
				matched[i + 1][j + 1] = matched[i][j];
			} else {
				matched[i + 1][j + 1] = Math.min(Math.min(matched[i][j + 1], matched[i + 1][j]), matched[i][j]) + 1;
				//Since it is bottom up, we are considering in the ascending order of indexes.
				//Insert means plus 1 to j, delete means plus 1 to i, replace means plus 1 to both i and j. 
				//above sequence is delete, insert and replace. 
			}
		}
	}
	
	return matched[c1.length][c2.length];
}