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

计算字符串的编辑距离

https://www.nowcoder.com/practice/3959837097c7413a961a135d7104c314?tpId=37&tags=&title=&difficulty=&judgeStatus=&rp=1&sourceUrl=%2Fexam%2Foj%2Fta%3Fpage%3D2%26pageSize%3D100%26search%3D%26tpId%3D37%26type%3D37&gioEnter=menu

import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNext()) {
            String s1 = in.nextLine();
            String s2 = in.nextLine();
            System.out.println(Levenshtein(s1, s2));
        }
        in.close();
    }

    /**
     * dp[i][j] -- 字符串0-i与另一字符串0-j相比的最小编辑距离
     * dp[i][j] = min{dp[i-1][j]+1,dp[i-1][j-1]+?,dp[i][j-1]+1}
     * dp[i-1][j]+1 ---相当于直接把i删了,让i变成i-1和j去比较
     * dp[i-1][j-1]+? --- 就是看新加的i和j是否相等,相等的话,?=0,不等的话就是1
     * dp[i][j-1]+1 --- dp[i][j-1]知道了,那么只要把j删了,变成[i][j-1]就行了
     */
    public static int Levenshtein(String s1, String s2) {
        int[][] dp = new int[s1.length() + 1][s2.length() + 1];
        //初始化dp第一列的值
        for (int i = 0; i < dp.length; i++) {
            dp[i][0] = i;
        }
        //初始化dp第一行的值
        for (int i = 0; i < dp[0].length; i++) {
            dp[0][i] = i;
        }

        for (int i = 1; i < dp.length ; i++) {
            for (int j = 1; j < dp[0].length; j++) {
                dp[i][j] = Math.min(dp[i][j - 1] + 1, dp[i - 1][j] + 1);
                int may = s1.charAt(i - 1) == s2.charAt(j - 1) ? 0 : 1;
                dp[i][j] = Math.min(dp[i][j], dp[i - 1][j - 1] + may);
            }
        }

        return dp[s1.length()][s2.length()];

    }
}

全部评论

相关推荐

07-18 18:05
门头沟学院 Java
挂了&nbsp;正式批求捞
投递滴滴等公司10个岗位
点赞 评论 收藏
分享
来个厂收我吧:首先,市场侧求职我不是很懂。 但是,如果hr把这份简历给我,我会觉得求职人不适合做产品经理。 问题点: 1,简历的字体格式不统一,排版不尽如人意 2,重点不突出,建议参考star法则写个人经历 3,印尼官方货币名称为印度尼西亚卢比(IDR),且GMV690000印尼盾换算为305人民币,总成交额不高。 4,右上角的意向职位在发给其他公司时记得删除。 5,你所有的经历都是新媒体运营,但是你要投市场营销岗位,jd和简历不匹配,建议用AI+提示词,参照多个jd改一下经历内容。 修改建议: 1,统一字体(中文:思源黑体或微软雅黑,英文数字:time new romans),在word中通过表格进行排版(b站学) 2,校招个人经历权重:实习经历=创业经历(大创另算)>项目经历>实训经历>校园经历 3,请将项目经历时间顺序改为倒序,最新的放最上方。 4,求职方向不同,简历文字描述侧重点也需要不同。
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

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