首页 > 代码库 > 【LeetCode】Edit Distance
【LeetCode】Edit Distance
Edit Distance
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
递归超时。
又是一个“走地图”的动态规划算法。
word1, word2只有两个字符串，因此可以展平为一个二维地图，转换代价即从左上角走到右下角的最小代价。
记代价矩阵为dist. dis[i][j]代表word1[0,i)转换为word2[0,j)的最小代价。
当word1到达第i-1个元素，word2到达第j-1个元素:
地图上往右一步代表word1当前位置插入了word2[j-1]字符，dis[i][j]=dis[i][j-1]+1, 下一次比较word1[i-1]和word2[j]
地图上往下一步代表word1当前位置删除了word1[i-1]字符，dis[i][j]=dis[i-1][j]+1, 下一次比较word1[i]和word2[j-1]
地图上往对角线一步代表word1[i-1]替换为word2[j-1]（相同则不替换），dis[i][j]=dis[i-1][j-1]+((word1[i-1]==word2[j-1])?0:1),下一次比较word1[i]和word2[j]
示例：word1="a", word2="ab"
dis 0 a b
0 0 1 2
a 1 0 1
class Solution {public: int minDistance(string word1, string word2) { if(word1 == "" && word2 == "") return 0; else if(word1 == "" && word2 != "") return word2.size(); else if(word1 != "" && word2 == "") return word1.size(); else { int size1 = word1.size(); int size2 = word2.size(); vector<vector<int> > dis(size1+1, vector<int>(size2+1, 0)); for(int i = 0; i <= size1; i ++) dis[i][0] = i; for(int j = 0; j <= size2; j ++) dis[0][j] = j; for(int i = 1; i <= size1; i ++) { for(int j = 1; j <= size2; j ++) { //move right from dis[i][j-1], insert word2[j-1] int dis1 = dis[i][j-1] + 1; //move down from dis[i-1][j], delete word1[i-1] int dis2 = dis[i-1][j] + 1; //move diagonal, replace word1[i-1] with word2[j-1] int replace = (word1[i-1]==word2[j-1])?0:1; int dis3 = dis[i-1][j-1] + replace; dis[i][j] = min(dis1, min(dis2,dis3)); } } return dis[size1][size2]; } }};
【LeetCode】Edit Distance