徐世龙


私信TA

用户名:dotcpp0681143

访问量:425

签 名:

等  级
排  名 7866
经  验 1239
参赛次数 0
文章发表 12
年  龄 0
在职情况 学生
学  校 xdu
专  业

  自我简介:

解题思路: 


三种操作分别是:

  1. 插入 

  2. 删除

  3. 替换


需要清楚的点: 

  1. 两字符串A和B,给A插入相当于给B删除,反之亦然(例如cat和cate)

  2. 替换A相当于替换B(例如cat和fat)

故本质操作就三种 : ① A插 ② B插 ③ 替换


dp[i][j]表示从 A 的 前 i 个 字 符 转换到 B 的 前 j 个 字 符 所需的最短步数

(例如A是qwert B是aserty 那么最终输出结果就是dp[5][6])


 dp[i-1][j-1]到dp[i][j]需要进行替换操作

若A的第 i 位(其实就是当前操作位)等于 B的第 j 位(其实就是当前操作位),那么就不需要替换,因此dp[i][j] = dp[i-1][j-1] ,否则dp[i][j] = dp[i-1][j-1]+1


 dp[i-1][j]到d[i][j]需要进行删除操作

dp[i][j] = dp[i-1][j] + 1 


 dp[i][j-1]到d[i][j]需要进行添加操作

dp[i][j] = dp[i][j-1] + 1 




★当A与B末位相同时:


dp[i][j] = min(dp[i][j−1]+1,dp[i−1][j]+1,dp[i−1][j−1]) 



★当A与B末位不相同时:

dp[i][j] =1+min(dp[i][j−1],dp[i−1][j],dp[i−1][j−1])




***那么,我们要怎么从dp[0][0] 到 dp[i][j]呢?

很简单,每一步做出判断,替换、删除、添加哪个短就选哪个!

这里需要注意,①dp[a][b]代表着前面所有步数的最短选择!②由于不知道AB长度,因此A插和B插不可以混为一谈!




注意事项: 

边界情况,A或B为空,直接输出不为空的数组长度即可



参考代码:

#include

using namespace std;

int main(){


    //注意!!数组是从0开始索引的,所以第i位就是i-1的索引,以此类推!!


    string a,b;

    getline(cin,a);

    getline(cin,b);

    int len1 = a.length();

    int len2 = b.length(); //接受输入记录长度

   

    int dp[len1][len2]; //定义dp数组


    for (int i = 0; i < len1; i++) {dp[i][0] = i;}

    for (int j = 0; j < len2; j++) {dp[0][j] = j;}  //边界情况,同时也是初始化


    for (int i = 1; i < len1; i++)

    {

        for (int j = 1; j < len2; j++) //ij从1开始,因为已经初始化过了,从0开始会溢出

        {

            if(a[i-1] == b[j-1]) //A的第i位与B的第j位相同的情况

            dp[i][j] = min(min(dp[i][j-1]+1, dp[i-1][j]+1),dp[i-1][j-1]);

            else

            dp[i][j] = min(min(dp[i][j-1]+1, dp[i-1][j]+1),dp[i-1][j-1]+1);

        }

       

    }

    cout<<dp[len1-1][len2-1]<<endl;


    return 0;

}





 

0.0分

1 人评分

  评论区

abc123
123abc
最短编辑距离是6,你这个得到5,有问题。
2024-01-31 15:47:15
  • «
  • 1
  • »