Java | Leetcode Java题解之第127题单词接龙

题目:

题解:

class Solution {
    Map<String, Integer> wordId = new HashMap<String, Integer>();
    List<List<Integer>> edge = new ArrayList<List<Integer>>();
    int nodeNum = 0;

    public int ladderLength(String beginWord, String endWord, List<String> wordList) {
        for (String word : wordList) {
            addEdge(word);
        }
        addEdge(beginWord);
        if (!wordId.containsKey(endWord)) {
            return 0;
        }

        int[] disBegin = new int[nodeNum];
        Arrays.fill(disBegin, Integer.MAX_VALUE);
        int beginId = wordId.get(beginWord);
        disBegin[beginId] = 0;
        Queue<Integer> queBegin = new LinkedList<Integer>();
        queBegin.offer(beginId);
        
        int[] disEnd = new int[nodeNum];
        Arrays.fill(disEnd, Integer.MAX_VALUE);
        int endId = wordId.get(endWord);
        disEnd[endId] = 0;
        Queue<Integer> queEnd = new LinkedList<Integer>();
        queEnd.offer(endId);

        while (!queBegin.isEmpty() && !queEnd.isEmpty()) {
            int queBeginSize = queBegin.size();
            for (int i = 0; i < queBeginSize; ++i) {
                int nodeBegin = queBegin.poll();
                if (disEnd[nodeBegin] != Integer.MAX_VALUE) {
                    return (disBegin[nodeBegin] + disEnd[nodeBegin]) / 2 + 1;
                }
                for (int it : edge.get(nodeBegin)) {
                    if (disBegin[it] == Integer.MAX_VALUE) {
                        disBegin[it] = disBegin[nodeBegin] + 1;
                        queBegin.offer(it);
                    }
                }
            }

            int queEndSize = queEnd.size();
            for (int i = 0; i < queEndSize; ++i) {
                int nodeEnd = queEnd.poll();
                if (disBegin[nodeEnd] != Integer.MAX_VALUE) {
                    return (disBegin[nodeEnd] + disEnd[nodeEnd]) / 2 + 1;
                }
                for (int it : edge.get(nodeEnd)) {
                    if (disEnd[it] == Integer.MAX_VALUE) {
                        disEnd[it] = disEnd[nodeEnd] + 1;
                        queEnd.offer(it);
                    }
                }
            }
        }
        return 0;
    }

    public void addEdge(String word) {
        addWord(word);
        int id1 = wordId.get(word);
        char[] array = word.toCharArray();
        int length = array.length;
        for (int i = 0; i < length; ++i) {
            char tmp = array[i];
            array[i] = '*';
            String newWord = new String(array);
            addWord(newWord);
            int id2 = wordId.get(newWord);
            edge.get(id1).add(id2);
            edge.get(id2).add(id1);
            array[i] = tmp;
        }
    }

    public void addWord(String word) {
        if (!wordId.containsKey(word)) {
            wordId.put(word, nodeNum++);
            edge.add(new ArrayList<Integer>());
        }
    }
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/673586.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

计算机网络学习实践:配置主机通过DHCP获取IP并通过域名访问web服务器

计算机网络学习实践&#xff1a;配置主机通过DHCP获取IP并通过域名访问web服务器 点一点就能配置&#xff0c;不需要输入命令 1.实验准备 实验环境&#xff1a;思科的模拟器 实验设备&#xff1a; 3个服务器&#xff0c;1个二层交换机&#xff08;不是三层的&#xff09;&a…

ctfshow-web入门-信息搜集(web11-web20)

目录 1、web11 2、web12 3、web13 4、web14 5、web15 6、web16 7、web17 8、web18 9、web19 10、web20 1、web11 域名其实也可以隐藏信息&#xff0c;比如flag.ctfshow.com 就隐藏了一条信息 查询域名的 DNS 记录&#xff0c;类型为 TXT&#xff08;域名的说明&#…

20、matlab信号波形生成:狄利克雷函数、高斯脉冲和高斯脉冲序列

1、狄利克雷函数生成波形diric()函数 语法&#xff1a;y diric(x,n) 返回n次的狄利克雷函数对输入数组x的元素求值。 1&#xff09;diric()函数 代码 x linspace(-2*pi,2*pi,301);%定义x取值 d6 diric(x,6); d7 diric(x,7); subplot(2,1,1) plot(x,d6) ylabel(n 6) tit…

YOLOv10:实时端到端目标检测的新突破

目标检测作为计算机视觉领域的一个核心问题&#xff0c;其关键在于能够在图像中准确识别并定位对象。随着深度学习技术的发展&#xff0c;基于深度神经网络的目标检测方法不断涌现&#xff0c;其中YOLO&#xff08;You Only Look Once&#xff09;系列算法以其优异的实时性和准…

【PB案例学习笔记】-14使用次数和日期限制

写在前面 这是PB案例学习笔记系列文章的第14篇&#xff0c;该系列文章适合具有一定PB基础的读者。 通过一个个由浅入深的编程实战案例学习&#xff0c;提高编程技巧&#xff0c;以保证小伙伴们能应付公司的各种开发需求。 文章中设计到的源码&#xff0c;小凡都上传到了gite…

如何注册及使用飞浆AI Studio资源跑模型

之前已经介绍过如何注册及使用Kaggle平台的资源跑模型&#xff0c;今天我们将介绍如何注册及使用飞浆AI Studio资源​。 一、AI Studio简介 飞桨AI Studio是基于百度深度学习开源平台飞桨&#xff08;PaddlePaddle&#xff09;的人工智能学习与实训社区。我们先让文心一言给对…

数字组合问题(回溯法)

一、问题描述 找出从自然数1、2、……、n中任取r个数的所有组合。 问题的状态空间为&#xff1a; E{&#xff08;x1&#xff0c;x2&#xff0c;...&#xff0c;xr&#xff09;∣xi∈S &#xff0c;i1&#xff0c;2&#xff0c;...&#xff0c;r } 其中&#xff1a…

现成方案 - 复刻版类似 Perplexity 与秘塔 AI 的搜索引擎

这里为大家带来一个极具创新性的开源 AI 搜索引擎&#xff0c;其灵感源自 Perplexity。 该搜索引擎主要具备以下功能&#xff1a; 能够接收用户提出的各种问题。借助 Bing 搜索 API 可查找出前 6 个结果并予以展示。会抓取这 6 个链接的文本内容&#xff0c;将其作为重要的上下…

基于springboot实现青年公寓服务平台系统项目【项目源码+论文说明】计算机毕业设计

基于springboot实现青年公寓服务平台系统演示 摘要 传统信息的管理大部分依赖于管理人员的手工登记与管理&#xff0c;然而&#xff0c;随着近些年信息技术的迅猛发展&#xff0c;让许多比较老套的信息管理模式进行了更新迭代&#xff0c;房屋信息因为其管理内容繁杂&#xff…

Spark 3.5.1 升级 Java 17 异常 cannot access class sun.nio.ch.DirectBuffer

异常说明 使用Spark 3.5.1 升级到Java17的时候会有一个异常&#xff0c;异常如下 SLF4J: Failed to load class "org.slf4j.impl.StaticLoggerBinder". SLF4J: Defaulting to no-operation (NOP) logger implementation SLF4J: See http://www.slf4j.org/codes.htm…

面试题:谈谈你对观察者和订阅发布的理解

面试题&#xff1a;谈谈你对观察者和订阅发布的理解 1. 观察者设计模式 场景引入之杂志订阅&#xff1a;小王想要购买一本尚未出版的杂志&#xff0c;他向出版社预订该杂志并提供联系方式&#xff0c;一旦该杂志出版&#xff0c;出版社就会根据小王预留的联系方式通知他可以来…

YOLOv8_obb预测流程-原理解析[旋转目标检测理论篇]

YOLOv8_obb的预测流程,主要分预处理模块、推理模块和后处理模块。这里面有很多内容是和目标检测预测流程是重合的,主要区别在于Angle分支、NMS后处理以及regularize_rboxes部分。本文也主要介绍一下这三个模块,其他模块可以结合YOLOv8预测流程-原理解析[目标检测理论篇]一起…

最新版wordpress网创资源美化以及更新自动同步插件

最新更新了美化右侧悬浮图标 底部分类板块&#xff0c;以及文章自动同步插件 1.支持分类替换 将主站同步过来的文章分类进行替换 2.支持本地化文章图片 &#xff08;使用储存桶可能会导致无法保存图片&#xff09; 3.支持自定义文章作者&#xff08;选择多个作者则同步到的…

辩证 逻辑学 | 洞察 事物矛盾及变化规律 在形式逻辑基础上 学会辩证思维(40节课)

课程下载&#xff1a;辩证逻辑学洞察事物矛盾及变化规律在形式逻辑基础上学会辩证思维&#xff08;40节课&#xff09;-课程网盘链接提取码下载.txt资源-CSDN文库 更多资源下载&#xff1a;关注我。 在形式逻辑的基础上&#xff0c;学会 辩证思维 敏锐 洞察事物发展变化的规…

RPG Maker MV角色战斗动画记录

角色战斗动画记录 角色战斗状态判断的语句赋值 战斗管理战斗精灵创建精灵进行角色的更新 角色战斗状态 角色的战斗状态是由 Game_Battler 类中的 _actionState 属性的字符串决定的&#xff0c;它有哪些值呢&#xff1f; undecided 未确定或者说是操作状态inputting 输入waiti…

开源VS闭源:大模型之争,究竟谁更胜一筹?

随着人工智能技术的快速发展&#xff0c;大模型作为其中的核心组件&#xff0c;已经引起了业界的广泛关注。在大模型的研发过程中&#xff0c;开源与闭源成为了两个备受争议的话题。究竟开源与闭源谁更好&#xff1f;本文将从多个角度进行深入分析&#xff0c;为大家揭示真相。…

React + SpringBoot开发用户中心管理系统

用户中心项目搭建笔记 技术栈 前端技术栈 “react”: “^18.2.0”,ant-design-pro 后端技术栈 SpringBoot 2.6.x 项目源码地址 https://gitee.com/szxio/user-center 前端项目搭建 快速搭建一个后端管理系统项目框架 初始化 antDesignPro 官网&#xff1a; https://…

godot.bk:how to add map to the game

1.项目构建如下&#xff0c;map是我们点击start之后才渲染出来的 mian.tscn --main.gd --background(textureact) --start(button) --button.gd sourceFile map.tscn --tilemap --tileset 2.main.gd&#xff1a;注意main.gd并不定义信号&#xff0c;它只是接收信号而已 extend…

新书推荐:1.2 动态链接库与API

本节必须掌握的知识点&#xff1a; kernel32.dll user32.dll gdi32.dll ■动态链接库 最早的软件开发过程&#xff0c;所有的功能实现都是有程序员独立完成的。在这个过程中&#xff0c;我们很快就会发现&#xff0c;有很多常用的功能模块是可以重复利用的&#xff0c;我们将…

UE5.1_常用快捷键

UE5.1_常用快捷键 shift1&#xff0c;&#xff0c;模式选择 shift2&#xff0c;&#xff0c;模式选择 shift3&#xff0c;&#xff0c;模式选择 shift4&#xff0c;&#xff0c;模式选择 shift5&#xff0c;&#xff0c;模式选择 shift6&#xff0c;&#xff0c;模式选择 …