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

计算字符串的编辑距离

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

import java.util.*;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNextLine()) {
            String sA = sc.nextLine();
            String sB = sc.nextLine();
            System.out.println(dpMethod(sA, sB));
        }
        sc.close();
    }
    private static int dpMethod(String sA, String sB) {
        //定义一个dp数组
        int[][] dp = new int[sA.length() + 1][sB.length() + 1];
        //初始化
        for (int i = 1; i <= sA.length(); i++) {
            dp[i][0] = i;
        }
        for (int i = 1; i <= sB.length(); i++) {
            dp[0][i] = i;
        }

        for (int i = 1; i <= sA.length(); i++) {
            for (int j = 1; j <= sB.length(); j++) {
                if (sA.charAt(i - 1) == sB.charAt(j - 1)) { //第一种方式
                    dp[i][j] = dp[i - 1][j - 1];
                } else {//第二种方式
                    dp[i][j] = Math.min(dp[i - 1][j - 1] + 1, Math.min(dp[i - 1][j] + 1,
                                        dp[i][j - 1] + 1));
                }
            }
        }

        return  dp[sA.length()][sB.length()];
    }
}

全部评论

相关推荐

废物一个0offer:认真的吗二本本科找人工智能岗位
点赞 评论 收藏
分享
06-23 11:28
门头沟学院 Java
牛客91966197...:也有可能是点拒绝的时候自动弹的话术
点赞 评论 收藏
分享
不愿透露姓名的神秘牛友
07-01 13:54
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

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