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 security快速使用示例详解

《springbootsecurity快速使用示例详解》:本文主要介绍springbootsecurity快速使用示例,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝... 目录创www.chinasem.cn建spring boot项目生成脚手架配置依赖接口示例代码项目结构启用s

java之Objects.nonNull用法代码解读

《java之Objects.nonNull用法代码解读》:本文主要介绍java之Objects.nonNull用法代码,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐... 目录Java之Objects.nonwww.chinasem.cnNull用法代码Objects.nonN

springboot security之前后端分离配置方式

《springbootsecurity之前后端分离配置方式》:本文主要介绍springbootsecurity之前后端分离配置方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的... 目录前言自定义配置认证失败自定义处理登录相关接口匿名访问前置文章总结前言spring boot secu

一文详解SpringBoot响应压缩功能的配置与优化

《一文详解SpringBoot响应压缩功能的配置与优化》SpringBoot的响应压缩功能基于智能协商机制,需同时满足很多条件,本文主要为大家详细介绍了SpringBoot响应压缩功能的配置与优化,需... 目录一、核心工作机制1.1 自动协商触发条件1.2 压缩处理流程二、配置方案详解2.1 基础YAML

java中使用POI生成Excel并导出过程

《java中使用POI生成Excel并导出过程》:本文主要介绍java中使用POI生成Excel并导出过程,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录需求说明及实现方式需求完成通用代码版本1版本2结果展示type参数为atype参数为b总结注:本文章中代码均为

springboot简单集成Security配置的教程

《springboot简单集成Security配置的教程》:本文主要介绍springboot简单集成Security配置的教程,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,... 目录集成Security安全框架引入依赖编写配置类WebSecurityConfig(自定义资源权限规则

Java的IO模型、Netty原理解析

《Java的IO模型、Netty原理解析》Java的I/O是以流的方式进行数据输入输出的,Java的类库涉及很多领域的IO内容:标准的输入输出,文件的操作、网络上的数据传输流、字符串流、对象流等,这篇... 目录1.什么是IO2.同步与异步、阻塞与非阻塞3.三种IO模型BIO(blocking I/O)NI

java中反射(Reflection)机制举例详解

《java中反射(Reflection)机制举例详解》Java中的反射机制是指Java程序在运行期间可以获取到一个对象的全部信息,:本文主要介绍java中反射(Reflection)机制的相关资料... 目录一、什么是反射?二、反射的用途三、获取Class对象四、Class类型的对象使用场景1五、Class

SpringBoot中封装Cors自动配置方式

《SpringBoot中封装Cors自动配置方式》:本文主要介绍SpringBoot中封装Cors自动配置方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录SpringBoot封装Cors自动配置背景实现步骤1. 创建 GlobalCorsProperties

Spring事务中@Transactional注解不生效的原因分析与解决

《Spring事务中@Transactional注解不生效的原因分析与解决》在Spring框架中,@Transactional注解是管理数据库事务的核心方式,本文将深入分析事务自调用的底层原理,解释为... 目录1. 引言2. 事务自调用问题重现2.1 示例代码2.2 问题现象3. 为什么事务自调用会失效3