题解 | #计算字符串的编辑距离#
计算字符串的编辑距离
https://www.nowcoder.com/practice/3959837097c7413a961a135d7104c314
//不会做，题解看力扣学的，变态
//dp[i][j]表示str1的前i个和str2的前j个的编辑距离(0表示前0个字符，即空串)
//需要找公式，操作包括3种1增 2删 3环。对str2操作相当str1的逆反操作，那我们干脆只改str1
//1 增，s1+=s2[j],操作一次使其等于情况（1），即dp[i][j-1]+1
//则dp[i][j]=min(dp[i][j-1],dp[i-1][j],dp[i-1][j-1])+1(str1[i]!=str2[j])
//dp[i][j]表示str1的前i个和str2的前j个的编辑距离(0表示前0个字符，即空串)
//需要找公式，操作包括3种1增 2删 3环。对str2操作相当str1的逆反操作，那我们干脆只改str1
//（1）若str1[i]==str2[j],即最后字符相同，那么dp[i][j]=dp[i-1][j-1](str1[i]==str2[j])
//第0行、列即空串对比，等于下标。//(2)否则,有以下几种操作尝试
//1 增，s1+=s2[j],操作一次使其等于情况（1），即dp[i][j-1]+1
//2 删，s1删除1个，dp[i-1][j]+1
//3 换，使得s1[i]==s2[j],dp[i-1][j-1]+1
//则dp[i][j]=min(dp[i][j-1],dp[i-1][j],dp[i-1][j-1])+1(str1[i]!=str2[j])|
|
|
a | b | c | d | e | f |
|
|
0 | 1 | 2 | 3 | 4 | 5 | 6 |
| a | 1 | 0 | 1 | 2 | 3 | 4 | 5 |
| b | 2 | 1 | 0 | 1 | 2 | 3 | 4 |
| c | 3 | 2 | 1 | 0 | 1 | 2 | 3 |
| d | 4 | 3 | 2 | 1 | 0 | 1 | 2 |
| e | 5 | 4 | 3 | 2 | 1 | 0 | 1 |
| f | 6 | 5 | 4 | 3 | 2 | 1 | 0 |
| g | 7 | 6 | 5 | 4 | 3 | 2 | 1 |
#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
using namespace std;
int main(){
string s1,s2;
cin>>s1>>s2;
int l1=s1.size(),l2=s2.size();
int **dp=new int*[l1+1];
for(int i=0;i<=l1;i++){
dp[i]=new int[l2+1]{i}; //第0行、列即空串对比,初始第0列==下标
}
for(int i=0;i<=l2;i++){
dp[0][i]=i; //初始第0行==下标
}
for(int i=1;i<=l1;i++){
for(int j=1;j<=l2;j++){
if(s1[i-1]==s2[j-1]){
dp[i][j]=dp[i-1][j-1]; //最后字符相同
}else{
//(2)否则,有以下几种操作尝试
//1 增，s1+=s2[j],操作一次使其等于情况（1），即dp[i][j-1]+1
//2 删，s1删除1个，dp[i-1][j]+1
//3 换，使得s1[i]==s2[j],dp[i-1][j-1]+1
dp[i][j]=min(dp[i][j-1],min(dp[i-1][j],dp[i-1][j-1]))+1;
}
}
}
cout<<dp[l1][l2];
return 0;
}
