题解 | 计算字符串的编辑距离

计算字符串的编辑距离

https://www.nowcoder.com/practice/3959837097c7413a961a135d7104c314

import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        while(scanner.hasNext()) {
            String firstStr = scanner.nextLine();
            String secondStr = scanner.nextLine();
            int firstLength = firstStr.length();
            int secondLength = secondStr.length();
            int[][] dp = new int[firstLength + 1][secondLength + 1];
            dp[0][0] = 0;
            //secondStr只有0个字符时,初始化从secondStr变为firstStr时需要的最少的编辑次数,通过添加的形式
            for(int i = 1;i <= firstLength; i ++)
            {
                dp[i][0] = i;
            }
            //firstStr只有0个字符时,初始化从secondStr变为firstStr时需要的最少的编辑次数,通过删除的形式
            for(int j = 1;j <= secondLength; j ++)
            {
                dp[0][j] = j;
            }

            //因为至少有1个字符,所以从下标1开始
            for(int i = 1; i <= firstLength; i ++)
            {
                for(int j = 1; j <= secondLength; j ++)
                {
                    //情形1:firstStr有i-1个字符,secondStr有j个字符,转为一样需要的最小编辑次数为dp[i - 1][j],
                    //为什么要加1? firstStr现在为i个字符,secondStr为j个字符,转为一样可以有如下方法(不管哪一种操作,需要的编辑次数都为1)
                    // 1. firstStr去掉第i个字符,编辑次数为1
                    // 2. secondStr添加第i个字符,编辑次数为1
                    int val1 = dp[i - 1][j] + 1;
                    int val2 = dp[i][j - 1] + 1;
                    int val3 = dp[i - 1][j - 1];
                    //比较firstStr的第i个字符和secondStr的第j个字符是否相等,请注意下标(i-1)才是第i个字符
                    if(!(firstStr.charAt(i - 1) == secondStr.charAt(j - 1)))
                    {
                        val3 = val3 + 1;
                    }
                    //取val1,val2,val3三者最小值,即:firstStr有i个字符,secondeStr有j个字符,它们转为相同时所需要的最小编辑次数
                    dp[i][j] = Math.min(Math.min(val1,val2),val3);
                }
            }
            System.out.println(dp[firstLength][secondLength]);
        }
    }
}

全部评论

相关推荐

不愿透露姓名的神秘牛友
昨天 15:58
投个小米提前批试试水,先投一个岗位看看形势,不行就再沉淀一下投第二个岗位,莫辜负
Java抽象带篮子:我嘞个骚刚,已经开始研发6g了吗
投递小米集团等公司7个岗位
点赞 评论 收藏
分享
06-23 11:28
门头沟学院 Java
牛客91966197...:也有可能是点拒绝的时候自动弹的话术
点赞 评论 收藏
分享
Southyeung:我说一下我的看法(有冒犯实属抱歉):(1)简历不太美观,给我一种看都不想看的感觉,感觉字体还是排版问题;(2)numpy就一个基础包,机器学习算法是什么鬼?我感觉你把svm那些写上去都要好一点。(2)课程不要写,没人看,换成获奖经历;(3)项目太少了,至少2-3个,是在不行把网上学习的也写上去。
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务