Edit Distance — leetcode

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

    假设我们要将字符串str1变成str2
    sstr1(i)是str1的子串,范围[0到i),sstr1(0)是空串
    sstr2(j)是str2的子串,同上
    d(i,j)表示将sstr1(i)变成sstr2(j)的编辑距离

    首先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点,

    1. 如果将c替换成d,编辑距离是somestr1变成somestr2的编辑距离 + 1,也就是d(i⑴,j⑴) + 1
    2. 如果在c后面添加1个字d,编辑距离就应当是somestr1c变成somestr2的编辑距离 + 1,也就是d(i,j⑴) + 1
    3. 如果将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();
}
};

波比源码 – 精品源码模版分享 | www.bobi11.com
1. 本站所有资源来源于用户上传和网络,如有侵权请邮件联系站长!
2. 分享目的仅供大家学习和交流,您必须在下载后24小时内删除!
3. 不得使用于非法商业用途,不得违反国家法律。否则后果自负!
4. 本站提供的源码、模板、插件等等其他资源,都不包含技术服务请大家谅解!
5. 如有链接无法下载、失效或广告,请联系管理员处理!
6. 本站资源售价只是赞助,收取费用仅维持本站的日常运营所需!
7. 本站源码并不保证全部能正常使用,仅供有技术基础的人学习研究,请谨慎下载
8. 如遇到加密压缩包,请使用WINRAR解压,如遇到无法解压的请联系管理员!

波比源码 » Edit Distance — leetcode
赞助VIP 享更多特权,建议使用 QQ 登录
喜欢我嘛?喜欢就按“ctrl+D”收藏我吧!♡