72. Edit Distance

we use a array dist to save the minimum distance of substring of word1 and word2, i.e., dist[i][j] denotes the minimum distance of word1.substring(0, i) and word2.substring(0, j).

Apparently, dist[0][j] = j and dist[i][0] = i.

When we calculate dist[i][j], we first compare word1[i] and word2[j], if word1[i] equals word2[j], then dist[i][j] equals dist[i - 1][j - 1]. If word1[i] != word2[j], then we have three operations:

1. replace word1[i] with word2[j] (dist[i - 1][j - 1] + 1)
2. delete word1[i] (dist[i - 1][j] + 1)
3. delete word2[j] (dist[i][j - 1] + 1)

Note that insert and delete are symmetric operations, so we choice 2 is equal to insert character to word2 and choice 3 is equal to insert character to word1.

public int minDistance(String word1, String word2) {
    int dist[][] = new int[word1.length() + 1][word2.length() + 1];
    for(int i = 0; i < word1.length(); i++) 
	dist[i + 1][0] = i + 1;
    for(int i = 0; i < word2.length(); i++)
	dist[0][i + 1] = i + 1;
    for(int i = 0; i < word1.length(); i++) {
	for(int j = 0; j < word2.length(); j++) {
	    if( word1.charAt(i) == word2.charAt(j) )
		dist[i + 1][j + 1] = dist[i][j];
	    else
		dist[i + 1][j + 1] = Math.min(Math.min(dist[i][j + 1], dist[i + 1][j]) + 1, dist[i][j] + 1);
	}
    }
    return dist[word1.length()][word2.length()];
}