java常用算法之字梯(广度优先搜索bfs)

2024-09-06 09:18

本文主要是介绍java常用算法之字梯(广度优先搜索bfs),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

<span style="font-family: 'microsoft yahei', simhei, arial, sans-serif; font-size: 16px;">给定2个单词(start</span><span style="font-family: 'microsoft yahei', simhei, arial, sans-serif; font-size: 16px;">和end),和一个字典,找到最短的变换序列的长度,从start到end,这样的一次</span><span style="font-size: 16px; font-family: 'microsoft yahei', simhei, arial, sans-serif;">只有一个字母可以改变并且</span><span style="font-size: 16px; font-family: 'microsoft yahei', simhei, arial, sans-serif;">每个中间字必须存在于字典。例如,给定:</span><pre style="margin: 0px 0em 25px; padding: 8px; border: 1px solid rgb(209, 209, 232); font-size: 13px; border-radius: 4px; color: rgb(34, 34, 34); line-height: 25.5px; background-color: rgb(250, 248, 227);">start = "hit"
end = "cog"
dict = ["hot","dot","dog","lot","log"]<span style="font-family: 'microsoft yahei', simhei, arial, sans-serif; font-size: 16px;"> </span>
 
<span style="font-family: 'microsoft yahei', simhei, arial, sans-serif; font-size: 16px;"> 程序将会找到"hit" -> "hot" -> "dot" -> "dog" -> "cog",输出最短变换距离4</span>
package utils;import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.Queue;import com.google.gson.Gson;public class WordLadder {// solution functionpublic static int ladderLength(String start, String end,HashSet<String> dict) {// saving the graph nodes on hash map.HashMap<String, GraphNode> nodes = new HashMap<>();// adding the start and the end words to the dictdict.add(start);dict.add(end);for (String word : dict) {nodes.put(word, new GraphNode(word));}// update each node's adjacents according to one character different// relationObject[] dictArray = dict.toArray();for (int i = 0; i < dictArray.length; i++) {for (int j = i + 1; j < dictArray.length; j++) {if (isNeighbor((String) dictArray[i], (String) dictArray[j])) {nodes.get((String) dictArray[i]).childs.add(nodes.get((String) dictArray[j]));nodes.get((String) dictArray[j]).childs.add(nodes.get((String) dictArray[i]));}}}// Run BFS on the Graph and take the dist generated as resultHashMap<String, Integer> result = BFS(nodes, start);// Return the distance of the end word node from the start word nodereturn result.get(end);}// BFS functionpublic static HashMap<String, Integer> BFS(HashMap<String, GraphNode> nodes, String start) {HashMap<String, Integer> visited = new HashMap<>();HashMap<String, Integer> dist = new HashMap<>();for (String key : nodes.keySet()) {visited.put(key, 0);dist.put(key, 0);}Queue<String> q = new LinkedList<>();q.add(start);visited.put(start, 1);while (!q.isEmpty()) {String dequeued = q.remove();GraphNode curNode = nodes.get(dequeued);LinkedList<GraphNode> currAdjs = curNode.childs;for (int i = 0; i < currAdjs.size(); i++) {GraphNode adj = (GraphNode) currAdjs.get(i);if (visited.get(adj.word) == 0) {visited.put(adj.word, 1);dist.put(adj.word, dist.get(dequeued) + 1);q.add(adj.word);}}}return dist;}// check if two words differ by one characterpublic static boolean isNeighbor(String a, String b) {assert a.length() == b.length();int differ = 0;for (int i = 0; i < a.length(); i++) {if (a.charAt(i) != b.charAt(i))differ++;if (differ > 1)return false;}return true;}public static void main(String[] args) {// dict = ["hot","dot","dog","lot","log"] result 5;HashSet<String> dict = new HashSet<String>();dict.add("hot");dict.add("dot");dict.add("dog");dict.add("lot");dict.add("log");System.out.println(ladderLength("hit", "cog", dict));}}class GraphNode {String word;LinkedList<GraphNode> childs;public GraphNode(String word) {this.word = word;childs = new LinkedList<GraphNode>();}}

这篇关于java常用算法之字梯(广度优先搜索bfs)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1141612

相关文章

SpringBoot全局域名替换的实现

《SpringBoot全局域名替换的实现》本文主要介绍了SpringBoot全局域名替换的实现,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一... 目录 项目结构⚙️ 配置文件application.yml️ 配置类AppProperties.Ja

Java使用Javassist动态生成HelloWorld类

《Java使用Javassist动态生成HelloWorld类》Javassist是一个非常强大的字节码操作和定义库,它允许开发者在运行时创建新的类或者修改现有的类,本文将简单介绍如何使用Javass... 目录1. Javassist简介2. 环境准备3. 动态生成HelloWorld类3.1 创建CtC

JavaScript中的高级调试方法全攻略指南

《JavaScript中的高级调试方法全攻略指南》什么是高级JavaScript调试技巧,它比console.log有何优势,如何使用断点调试定位问题,通过本文,我们将深入解答这些问题,带您从理论到实... 目录观点与案例结合观点1观点2观点3观点4观点5高级调试技巧详解实战案例断点调试:定位变量错误性能分

Java实现将HTML文件与字符串转换为图片

《Java实现将HTML文件与字符串转换为图片》在Java开发中,我们经常会遇到将HTML内容转换为图片的需求,本文小编就来和大家详细讲讲如何使用FreeSpire.DocforJava库来实现这一功... 目录前言核心实现:html 转图片完整代码场景 1:转换本地 HTML 文件为图片场景 2:转换 H

Java使用jar命令配置服务器端口的完整指南

《Java使用jar命令配置服务器端口的完整指南》本文将详细介绍如何使用java-jar命令启动应用,并重点讲解如何配置服务器端口,同时提供一个实用的Web工具来简化这一过程,希望对大家有所帮助... 目录1. Java Jar文件简介1.1 什么是Jar文件1.2 创建可执行Jar文件2. 使用java

SpringBoot实现不同接口指定上传文件大小的具体步骤

《SpringBoot实现不同接口指定上传文件大小的具体步骤》:本文主要介绍在SpringBoot中通过自定义注解、AOP拦截和配置文件实现不同接口上传文件大小限制的方法,强调需设置全局阈值远大于... 目录一  springboot实现不同接口指定文件大小1.1 思路说明1.2 工程启动说明二 具体实施2

Java实现在Word文档中添加文本水印和图片水印的操作指南

《Java实现在Word文档中添加文本水印和图片水印的操作指南》在当今数字时代,文档的自动化处理与安全防护变得尤为重要,无论是为了保护版权、推广品牌,还是为了在文档中加入特定的标识,为Word文档添加... 目录引言Spire.Doc for Java:高效Word文档处理的利器代码实战:使用Java为Wo

SpringBoot日志级别与日志分组详解

《SpringBoot日志级别与日志分组详解》文章介绍了日志级别(ALL至OFF)及其作用,说明SpringBoot默认日志级别为INFO,可通过application.properties调整全局或... 目录日志级别1、级别内容2、调整日志级别调整默认日志级别调整指定类的日志级别项目开发过程中,利用日志

Java中的抽象类与abstract 关键字使用详解

《Java中的抽象类与abstract关键字使用详解》:本文主要介绍Java中的抽象类与abstract关键字使用详解,本文通过实例代码给大家介绍的非常详细,感兴趣的朋友跟随小编一起看看吧... 目录一、抽象类的概念二、使用 abstract2.1 修饰类 => 抽象类2.2 修饰方法 => 抽象方法,没有

SpringBoot 多环境开发实战(从配置、管理与控制)

《SpringBoot多环境开发实战(从配置、管理与控制)》本文详解SpringBoot多环境配置,涵盖单文件YAML、多文件模式、MavenProfile分组及激活策略,通过优先级控制灵活切换环境... 目录一、多环境开发基础(单文件 YAML 版)(一)配置原理与优势(二)实操示例二、多环境开发多文件版