编辑距离
题目
思路
dp[i][j]指前i个字符转换为目标的前j个字符的操作次数。 根据当前位置字符相同与否分情况，不同时再考虑插入、删除和替换。
代码
class Solution {
public:
int minDistance(string word1
, string word2
) {
int l1
=word1
.size();
int l2
=word2
.size();
int dp
[l1
+1][l2
+1];
for(int i
=0;i
<=l1
;i
++)
dp
[i
][0]=i
;
for(int i
=0;i
<=l2
;i
++)
dp
[0][i
]=i
;
for(int i
=1;i
<=l1
;i
++)
for(int j
=1;j
<=l2
;j
++)
{
if(word1
[i
-1]==word2
[j
-1]) dp
[i
][j
]=dp
[i
-1][j
-1];
else
{
int t
=min(dp
[i
-1][j
],dp
[i
][j
-1]);
dp
[i
][j
]=min(t
,dp
[i
-1][j
-1])+1;
}
}
return dp
[l1
][l2
];
}
};
