首页 > 代码库 > Leetcode | Edit Distance

Leetcode | Edit Distance

2024-07-02 22:32:51   228人阅读

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

这道题本来倒是一看就觉得应该是DP，因为有两个串，所以很自然地想用一个二维数组来保存中间结构，即用min[i][j]来表示word1[0...i]和word2[0...j]的最小edit distance.

进行递推求解的时候，初始是需要知道，min[i][0]和min[0][i]的值的，这个好算。不过注意当出现word1[i]=word2[0]或者word2[i] == word1[0]时有少许不同。比如word1="bbab"，word2="a"，那么min[0][0]=1,min[1][0]=2,min[2][0]=2,min[3][0]=3;

dp的公式如下:

min[i][j] = min[i-1][j-1], if word1[i] == word2[j];

　　　　 = min{min[i-1][j-1], min[i - 1][j], min[i][j - 1]}, else; //对应于三种情况（插入、删除、替换）

代码如下：

 1 class Solution {
 2 public:
 3     int minDistance(string word1, string word2) {
 4         int n1 = word1.length();
 5         int n2 = word2.length();
 6         if (n1 == 0) return n2;
 7         if (n2 == 0) return n1;
 8         vector<vector<int> > min(n1, vector<int>(n2, 0));
 9         
10         bool flag = false;
11         for (int i = 0; i < n1; ++i) {
12             if (word1[i] == word2[0]) { 
13                 min[i][0] = i;
14                 flag = true;
15             } else {
16                 if (flag) min[i][0] = i;
17                 else min[i][0] = i + 1;
18             }
19         }
20         
21         flag = false;
22         for (int i = 0; i < n2; ++i) {
23             if (word1[0] == word2[i]) { 
24                 min[0][i] = i;
25                 flag = true;
26             } else {
27                 if (flag) min[0][i] = i;
28                 else min[0][i] = i + 1;
29             }
30         }
31         
32         for (int i = 1; i < n1; ++i) {
33             for (int j = 1; j < n2; ++j) {
34                 if (word1[i] == word2[j]) {
35                     min[i][j] = min[i - 1][j - 1];
36                 } else {
37                     int m = min[i - 1][j] + 1;
38                     if (min[i][j - 1] + 1 < m) {
39                         m = min[i][j - 1] + 1;
40                     }
41                     if (min[i - 1][j - 1] + 1 < m) {
42                         m = min[i - 1][j - 1] + 1;
43                     }
44                     min[i][j] = m;
45                 }
46             }
47         }
48         
49         return min[n1 - 1][n2 - 1];
50     }
51     
52 };

 后来看到网上有人把min[i][j]中i和j理解为长度，这样多用了一些空间，不过效率高了一些，不需要在初始化的时候做分别处理。

 


联系
我们