题解 | 编辑距离(一)
编辑距离(一)
https://www.nowcoder.com/practice/6a1483b5be1547b1acd7940f867be0da
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param str1 string字符串
* @param str2 string字符串
* @return int整型
*/
int editDistance(string str1, string str2) {
int n=str1.length();
int m=str2.length();
vector<vector<int>> dp(n+1,vector<int>(m+1,0));
for(int i=0;i<=n;i++) dp[i][0]=i;
for(int j=0;j<=m;j++) dp[0][j]=j;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
if(str1[i-1]==str2[j-1]) dp[i][j]=dp[i-1][j-1];
else dp[i][j]=min({dp[i-1][j-1],dp[i-1][j],dp[i][j-1]})+1;
}
}
return dp[n][m];
}
};
查看6道真题和解析
