题解 | #计算字符串的编辑距离#
计算字符串的编辑距离
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; }