编辑距离
问题描述:leetcode:72Given 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;求把word1转化为word2需要的最少的步骤。对于字符串可以有以下操作:
a) 插入一个字符 b) 删除一个字符 c) 替换一个字符
思路:
先考虑边界情况,当word1有输入,word2为空时;所需要的步骤为word1的长度。
先考虑边界情况,当word1为空,word2有输入时;所需要的步骤为word2的长度。
当word1和word2都有输入时,对于dp[i][j]为何值取决于word1[i-1]与word2[j-1]是否相等,当不相等时:
dp[
i][
j] = dp[
i-1][
j] , dp[
i][
j-1], dp[
i-1][
j-1]中的最小值加1;
如下图所示: 由于a 与 d 不相等,所以dp[1][4]的值取决于图中所示三个值,取三个值中的最小值然后加1.
当word1[i-1]与word2[j-1]相等时:
dp[
i][
j]=dp[
i-1][
j-1]
如图所示:
我自己的渣代码,虽然AC但是可以看到一堆补丁:
int minDistance(string word1, string word2) {
int row = word1.length()
int col = word2.length()
if(row==
0&&col==
0)
return 0
else if(row==
0)
return col
else if(col==
0)
return row
int
a =
0
int b =
0
int ans[row][col]
string::iterator rowbegin=word1.begin()
string::iterator colbegin=word2.begin()
for (string::iterator i=word2.begin()
if (*i == *rowbegin) {
ans[
a][b] = b
}
else if(b==
0){
ans[
a][b] =
1
}
else{
ans[
a][b] = ans[
a][b-
1]+
1
}
b++
}
a =
1
b =
0
for (string::iterator j=word1.begin()+
1
if (*j == *colbegin) {
ans[
a][b] =
a
}
else{
ans[
a][b] = ans[
a-
1][b]+
1
}
a++
}
a =
1
b =
1
for (string::iterator i=rowbegin+
1
b =
1
for (string::iterator j=colbegin+
1
if (*i==*j) {
ans[
a][b] = ans[
a-
1][b-
1]
}
else{
ans[
a][b] = min(min(ans[
a-
1][b],ans[
a][b-
1]),ans[
a-
1][b-
1])+
1
}
b++
}
a++
}
return ans[row-
1][col-
1]
}
leetcode优秀代码:
int minDistance(
string word1,
string word2) {
int m = word1.length(), n = word2.length();
vector<vector<int> > dp(m +
1,
vector<int> (n +
1,
0));
for (
int i =
1; i <= m; i++)
dp[i][
0] = i;
for (
int j =
1; j <= n; j++)
dp[
0][j] = j;
for (
int i =
1; i <= m; i++) {
for (
int j =
1; j <= n; j++) {
if (word1[i -
1] == word2[j -
1])
dp[i][j] = dp[i -
1][j -
1];
else dp[i][j] = min(dp[i -
1][j -
1] +
1, min(dp[i][j -
1] +
1, dp[i -
1][j] +
1));
}
}
return dp[m][n];
}
语法注意点:
string是可以使用str[i]来获取第i+1个字符的,不一定非得使用iterator:
if (word1[i -
1] == word2[j -
1]);
定义了一个二维数组,行列数都已知: 注意:最后两个 > >中间有个空格。
vector<vector<int> > dp(m +
1,
vector<int> (n +
1,
0));
以上之所以要m+1和n+1是因为考虑到边界,当一个word没有输入时的情况;所以数组的大小要大一点。
转载请注明原文地址: https://ju.6miu.com/read-600058.html