leetcode -- Edit Distance

Given two words word1 and word2, find the minimum number of steps required to convert word1 to word2. (each operation is counted as 1 step.)

You have the following 3 operations permitted on a word:

a) Insert a character
b) Delete a character
c) Replace a character

[解题思路]

这里用ed(s1, s2)来表示s1, s2之间的edit distance

base case：

ed("", "") = 0

ed("", s) = ed(s, "") = ||s||

状态迁移方程：

ed(s1 + ch1, s2 + ch2) = ed(s1, s2) if ch1 == ch2, 这时从s1+ch1, s2+ch2 到 s1, s2不需要做任何操作

$ed(s_{1}+ch1, s_{2}+ch2) = min(1 + ed(s_{1}, s_{2}), 1 + ed(s_{1}+ch1, s_{2}), 1 + ed(s_{1}, s_{2}+ch2))$

if $ch1 != ch2$ . Here we compare three options:

Replace ch1 with ch2, hence $1 + ed(s_{1}, s_{2})$ .
Insert ch2 into $s_{2}$ , hence $1 + ed(s_{1}+ch1, s_{2})$ .
Delete ch1 from $s_{1}$ , hence $1 + ed(s_{1}, s_{2}+ch2)$ .

 1 public int minDistance(String word1, String word2) {
 2         // Start typing your Java solution below
 3         // DO NOT write main() function
 4         int m = word1.length(), n = word2.length();
 5         int[][] ed = new int[m + 1][n + 1];
 6         for(int i = 0; i < m + 1; i++){
 7             for(int j = 0; j < n + 1; j++){
 8                 if(i == 0){
 9                     ed[i][j] = j;
10                 } else if(j == 0){
11                     ed[i][j] = i;
12                 } else {
13                     if(word1.charAt(i - 1) == word2.charAt(j - 1)){
14                         ed[i][j] = ed[i - 1][j - 1];
15                     } else {
16                         ed[i][j] = 1 + Math.min(ed[i - 1][j - 1], Math.min(ed[i][j - 1], ed[i - 1][j]));
17                     }
18                 }
19             }
20         }
21         return ed[m][n];
22     }

ref:

http://tianrunhe.wordpress.com/2012/07/15/dynamic-programing-for-edit-distance-edit-distance/