*Word Ladder II

2024-06-18 17:48
文章标签 ii word ladder

本文主要是介绍*Word Ladder II,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

题目:

Given two words (beginWord and endWord), and a dictionary's word list, find all shortest transformation sequence(s) from beginWord to endWord, such that:

  1. Only one letter can be changed at a time
  2. Each intermediate word must exist in the word list

For example,

Given:
beginWord = "hit"
endWord = "cog"
wordList = ["hot","dot","dog","lot","log"]

Return

  [["hit","hot","dot","dog","cog"],["hit","hot","lot","log","cog"]]

Note:

  • All words have the same length.
  • All words contain only lowercase alphabetic characters.
分析:

class WordNode{String word;int numSteps;WordNode pre;public WordNode(String word, int numSteps, WordNode pre){this.word = word;this.numSteps = numSteps;this.pre = pre;}
}public class Solution {public List<List<String>> findLadders(String start, String end, Set<String> dict) {List<List<String>> result = new ArrayList<List<String>>();LinkedList<WordNode> queue = new LinkedList<WordNode>();queue.add(new WordNode(start, 1, null));dict.add(end);int minStep = 0;HashSet<String> visited = new HashSet<String>();  HashSet<String> unvisited = new HashSet<String>();  unvisited.addAll(dict);int preNumSteps = 0;while(!queue.isEmpty()){WordNode top = queue.remove();String word = top.word;int currNumSteps = top.numSteps;if(word.equals(end)){if(minStep == 0){minStep = top.numSteps;}if(top.numSteps == minStep && minStep !=0){//nothingArrayList<String> t = new ArrayList<String>();t.add(top.word);while(top.pre !=null){t.add(0, top.pre.word);top = top.pre;}result.add(t);continue;}}if(preNumSteps < currNumSteps){unvisited.removeAll(visited);}preNumSteps = currNumSteps;char[] arr = word.toCharArray();for(int i=0; i<arr.length; i++){for(char c='a'; c<='z'; c++){char temp = arr[i];if(arr[i]!=c){arr[i]=c;}String newWord = new String(arr);if(unvisited.contains(newWord)){queue.add(new WordNode(newWord, top.numSteps+1, top));visited.add(newWord);}arr[i]=temp;}}}return result;}
}




这篇关于*Word Ladder II的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



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

相关文章

AI基础 L9 Local Search II 局部搜索

Local Beam search 对于当前的所有k个状态,生成它们的所有可能后继状态。 检查生成的后继状态中是否有任何状态是解决方案。 如果所有后继状态都不是解决方案,则从所有后继状态中选择k个最佳状态。 当达到预设的迭代次数或满足某个终止条件时,算法停止。 — Choose k successors randomly, biased towards good ones — Close

从0到1,AI我来了- (7)AI应用-ComfyUI-II(进阶)

上篇comfyUI 入门 ,了解了TA是个啥,这篇,我们通过ComfyUI 及其相关Lora 模型,生成一些更惊艳的图片。这篇主要了解这些内容:         1、哪里获取模型?         2、实践如何画一个美女?         3、附录:               1)相关SD(稳定扩散模型的组成部分)               2)模型放置目录(重要)

C - Word Ladder题解

C - Word Ladder 题解 解题思路: 先输入两个字符串S 和t 然后在S和T中寻找有多少个字符不同的个数(也就是需要变换多少次) 开始替换时: tips: 字符串下标以0开始 我们定义两个变量a和b,用于记录当前遍历到的字符 首先是判断:如果这时a已经==b了,那么就跳过,不用管; 如果a大于b的话:那么我们就让s中的第i项替换成b,接着就直接输出S就行了。 这样

学习记录:js算法(二十八):删除排序链表中的重复元素、删除排序链表中的重复元素II

文章目录 删除排序链表中的重复元素我的思路解法一:循环解法二:递归 网上思路 删除排序链表中的重复元素 II我的思路网上思路 总结 删除排序链表中的重复元素 给定一个已排序的链表的头 head , 删除所有重复的元素,使每个元素只出现一次 。返回 已排序的链表 。 图一 图二 示例 1:(图一)输入:head = [1,1,2]输出:[1,2]示例 2:(图

解决Office Word不能切换中文输入

我们在使用WORD的时可能会经常碰到WORD中无法输入中文的情况。因为,虽然我们安装了搜狗输入法,但是到我们在WORD中使用搜狗的输入法的切换中英文的按键的时候会发现根本没有效果,无法将输入法切换成中文的。下面我就介绍一下如何在WORD中把搜狗输入法切换到中文。

LeetCode:3177. 求出最长好子序列 II 哈希表+动态规划实现n*k时间复杂度

3177. 求出最长好子序列 II 题目链接 题目描述 给你一个整数数组 nums 和一个非负整数k 。如果一个整数序列 seq 满足在下标范围 [0, seq.length - 2] 中 最多只有 k 个下标i满足 seq[i] != seq[i + 1] ,那么我们称这个整数序列为好序列。请你返回 nums中好子序列的最长长度。 实例1: 输入:nums = [1,2,1,1,3],

代码训练营 Day26 | 47.排序II | 51. N-皇后 |

47.排序II 1.跟46题一样只不过加一个树层去重 class Solution(object):def backtracking(self,nums,path,result,used):# recursion stopif len(path) == len(nums):# collect our setresult.append(path[:])return for i in range(

Excel和Word日常使用记录:

Excel使用总结 表格颜色填充: 合并单元格: 选中你要合并的单元格区域。按下快捷键 Alt + H,然后松开这些键。再按下 M,接着按 C。这个组合键执行的操作是:Alt + H:打开“主页”选项卡。M:选择“合并单元格”选项。C:执行“合并并居中”操作。 插入行: 在Excel中,插入一行的快捷键是:Windows:选择整行(可以点击行号)。按下 Ctrl + Sh

word转PDF后mathtype公式乱码以及图片分辨率降低等一系列问题|完美解决

word转PDF后mathtype公式乱码以及图片分辨率降低等一系列问题|完美解决 问题描述 最近在投一篇期刊论文,直接提交word文档,当时没有查看提交预览,一审审稿意见全是:公式乱码、公式乱码、乱码啊!!!是我大意了,第二次提交,我就决定将word文档转成PDF后再提交,避免再次出现公式乱码的问题。接着问题又来了,我利用‘文件/导出’或‘文件/另存为’的方式将word转成PDF后,发现公式

【信创建设】信息系统信创建设整体技方案(word原件完整版)

信创,即“信息技术应用创新”。我国自主信息产业聚焦信息技术应用创新,旨在通过对IT硬件、软件等各个环节的重构,基于我国自有IT底层架构和标准,形成自有开放生态,从根本上解决本质安全问题,实现信息技术可掌控、可研究、可发展、可生产。信创发展是一项国家战略,也是当今形势下国家经济发展的新功能。信创产业发展已经成为各行各业数字化转型、提升产业链发展的关键。 软件全套资料部分文档清单: 工作安排任