Edit Distance -- leetcode

发布时间：2020-12-13 20:07:00 所属栏目：PHP教程来源：网络整理

导读：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 charac

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

首先d(0,t),0<=t<=str1.size()和d(k,0)是很明显的。
当我们要计算d(i,j)时，即计算sstr1(i)到sstr2(j)之间的编辑距离,
此时，设sstr1(i)情势是somestr1c；sstr2(i)形如somestr2d的话，
将somestr1变成somestr2的编辑距离已知是d(i⑴,j⑴)
将somestr1c变成somestr2的编辑距离已知是d(i,j⑴)
将somestr1变成somestr2d的编辑距离已知是d(i⑴,j)
那末利用这3个变量，就能够递推出d(i,j)了：
如果c==d，明显编辑距离和d(i⑴,j⑴)是1样的
如果c!=d，情况略微复杂1点，

如果将c替换成d，编辑距离是somestr1变成somestr2的编辑距离 + 1，也就是d(i⑴,j⑴) + 1
如果在c后面添加1个字d，编辑距离就应当是somestr1c变成somestr2的编辑距离 + 1，也就是d(i,j⑴) + 1
如果将c删除，那就是要将somestr1编辑成somestr2d，距离就是d(i⑴,j) + 1
那最后只需要看着3种谁最小，就采取对应的编辑方案了。

上面对算法的分析来自于博客uniEagle

在下面的实现代码中，我使用转动数组，代替了2维数组。而且只分配了1个数组。

另外，变量dist_i1_j1 表示 d(i⑴,j⑴)

dist_i_j 表示 d(i,j)

dist_i1_j 表示d(i⑴,j)

dist_i_j1 表示d(i,j⑴)

另外，下面代码中，其实变量

dist_i1_j ， <pre name="code" class="cpp">dist_i_j

都是可以省掉的。

不过留着，可以更直观1点。

在leetcode上的实际履行时间为28ms。

class Solution { public: int minDistance(string word1,string word2) { if (word1.size() < word2.size()) word1.swap(word2); if (!word2.size()) return word1.size(); vector<int> dist(word2.size()); for (int j=0; j<dist.size(); j++) dist[j] = j+1; for (int i=0; i<word1.size(); i++) { int dist_i1_j1 = i; int dist_i_j1 = dist_i1_j1 +1; for (int j=0; j<word2.size(); j++) { const int dist_i1_j = dist[j]; const int dist_i_j = word1[i] == word2[j] ? dist_i1_j1 : min(min(dist_i1_j1,dist_i1_j),dist_i_j1) + 1; dist_i_j1 = dist_i_j; dist_i1_j1 = dist[j]; dist[j] = dist_i_j; } } return dist.back(); } };

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!