首页 > 代码库 > Leetcode#72 Edit Distance
Leetcode#72 Edit Distance
原题地址
教科书般经典的动归题目，也可以看作是地图寻路问题。例如word1="ceab"，word2="abc"，构造如下地图。其中"^"表示起点，"$"表示终点，则题目转化成了寻找一条从起点到终点的最短路径。
a b c <- word2word1 -> c ^ . . e . . . a . . . b . . $
对于地图上任意坐标为(i,j)的点，可以：
1. 向右走一步，表示跳过word2的一个字符，即删除一个word2的字符或向word1插入一个字符。
2. 向下走一步，表示跳过word1的一个字符，即删除一个word1的字符或向word2插入一个字符。
3. 向右下走一步，表示同时跳过word1和word2的一个字符，即修改一个word1或word2的字符，如果这两个字符本来就相等则不用修改。
令distance[i][j]表示从该点到终点的最短距离（也就是word1[i..n]和word2[j..m]的编辑距离），则有递推公式：
distance[i][j] = min{distance[i+1][j] + 1, distance[i][j+1] + 1, distance[i+1][j+1] + (word1[i] == word2[j] ? 0 : 1)}
具体实现中，由于递推公式只用到了相邻层的结果，所以可以压缩状态，用一维数组保存distance。
代码：
1 int minDistance(string word1, string word2) { 2 int len1 = word1.length(); 3 int len2 = word2.length(); 4 5 if (len1 < len2) 6 return minDistance(word2, word1); 7 if (len2 == 0) 8 return len1; 9 10 vector<int> distance(len1 + 1, 0);11 for (int j = len2; j >= 0; j--)12 distance[j] = len2 - j;13 int rd = 0; // 表示distance[i+1][j+1]14 15 for (int i = len1 - 1; i >= 0; i--) {16 rd = distance[len2];17 distance[len2] = len1 - i;18 for (int j = len2 - 1; j >= 0; j--) {19 int tmp = distance[j];20 distance[j] = min(distance[j] + 1, distance[j + 1] + 1);21 distance[j] = min(distance[j], rd + (word1[i] == word2[j] ? 0 : 1));22 rd = tmp;23 }24 }25 26 return distance[0];27 }
Leetcode#72 Edit Distance
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。