首页 > 代码库 > Edit Distance

Edit Distance

2024-07-05 15:11:24   227人阅读

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

思路就是用这三种方式分别去找最小的，递归做，贴一下代码

 1 public int minDistance(String word1, String word2) {
 2         if (word1.equals(word2)) {
 3             return 0;
 4         }
 5         if (word1.length() < word2.length()) {
 6             String t = word2;
 7             word2 = word1;
 8             word1 = t;
 9         }
10         int pos = 0;
11         for (; pos < word2.length(); pos++) {
12             if (word1.charAt(pos) != word2.charAt(pos)) {
13                 break;
14             }
15         }
16         if (pos == word2.length()) {
17             return word1.length() - word2.length();
18         } else {
19             int add = 1 + minDistance(word1.substring(pos), word1.charAt(pos)
20                     + word2.substring(pos));
21             int delete = 1 + minDistance(
22                     pos == word1.length() - 1 ? "" : word1.substring(pos + 1),
23                     word2.substring(pos));
24             int change = 1 + minDistance(
25                     pos == word1.length() - 1 ? "" : word1.substring(pos + 1),
26                     pos == word2.length() - 1 ? "" : word2.substring(pos + 1));
27             add = add > delete ? delete : add;
28             change = change > add ? add : change;
29             return change;
30         }
31     }

然后发现超时了0.0    忽然想起来编程之美上有这个题，查了一下，在第三章，书上的代码和我这差不多啊。。。编程之美上的解法都过不了是么。。。

分析了一下，由于多次递归，时间大部分都消耗在递归上了。

假设word1的长度为i，word2的长度为j

则word1与word2的距离只可能与这三种情况有关：

1.word1.substring(0,i)与word2之间的距离（删除）

2.word1与word2.substring(0,j)之间的距离（添加）

3.word1.substring(0,i)与word2.substring(0,j)之间的距离（更改或不变）

因此，可以将刚才自底向上的解法转化为自顶向下去计算，这样就消除了递归

最初设计的是word1.length()-1*word2.length()-1的矩阵grid，但是在矩阵grid[0][0]赋值的时候遇到了问题，因为最短距离时，word1[0]与word2[0]不一定对应，因此，多加一行一列，grid[i][j]表示word1的(0,i)子串与word2的(0,j)子串的最小距离，如下表所示：

以word1=sea，word2=eat为例：

“”

“”

“”

“e”

""

"ea"

""

"eat"

"s"

""

"s"

"e"

"s"

"ea"

"s"

"eat"

"se"

""

"se"

"e"

"se"

"ea"

"se"

"eat"

"sea"

""

"sea"

"e"

"sea"

"ea"

"sea"

"eat"

 

 

 

 

 

 

 

 

 

 

gird[i][j] = min(grid[i-1][j]+1,grid[i][j-1]+1,gird[i-1][j-1]+(word1.charAt(i)==word2.charAt(j)?0:1));

第0行和第0列要判断边界条件，初始化grid[0][0]=0;

结果就是矩阵grid右下角元素的值，代码如下：

 1 public int minDistance(String word1, String word2) {
 2         if(word1.equals("")){
 3             return word2.length();
 4         }
 5         if(word2.equals("")){
 6             return word1.length();
 7         }
 8         int grid[][] = new int[word1.length()+1][word2.length()+1];
 9         for (int i = 0; i <= word1.length(); i++) {
10             for (int j = 0; j <= word2.length(); j++) {
11                 if (i == 0 && j == 0) {
12                     grid[i][j] = 0;                        
13                 } else if (i == 0) {
14                     grid[i][j] = grid[i][j - 1] + 1;
15                 } else if (j == 0) {
16                     grid[i][j] = grid[i - 1][j] + 1;
17                 } else {
18                     grid[i][j] = grid[i - 1][j] > grid[i][j - 1] ? grid[i][j - 1] + 1
19                             : grid[i - 1][j] + 1;
20                     int count = 0;
21                     if(word1.charAt(i-1)!=word2.charAt(j-1)){
22                         count = 1;
23                     }
24                     grid[i][j] = grid[i][j]<grid[i-1][j-1]+count?grid[i][j]:grid[i-1][j-1]+count;
25                 }
26             }
27         }
28         return grid[word1.length()][word2.length()];
29     }


联系
我们