这道题可以考虑两种方式解决
1. 深度优先遍历
2. 广度优先遍历
其中算法的效率取决于数组中单词的顺序,如果解决方案靠前,那么深度优先所用时间短;如果解在中间的位置,那么广度优先用时较短
深度优先采用回溯递归调用的方式
public int ladderLengthTraceback(String start, String end, Set<String> dict) { List<String> words = new ArrayList<String>(); List<String> result = new ArrayList<String>(); backtrack(start, end, dict, words, result); if(result.isEmpty()){ return 0; } return result.size()+1; } private void backtrack(String start, String end, Set<String> dict, List<String> words, List<String> result){ if(start.equals(end)){ if(result.isEmpty() || words.size() < result.size()){ result.clear(); result.addAll(words); } return; }else if (!result.isEmpty() && words.size()>= result.size()){ return; } List<String> cw = new ArrayList<String>(); for(int i=0; i<start.length(); i++){ char[] startCharArray = start.toCharArray(); for(int j=0; j<26; j++){ startCharArray[i] = (char)('a' +j); String word = new String(startCharArray); if((dict.contains(word) && !words.contains(word)) || word.equals(end)){ cw.add(word); } } } for(String word : cw){ int size = words.size(); words.add(word); backtrack(word, end, dict, words, result); words.remove(size); } }
广度优先采用队列循环的方式
public int ladderLength(String start, String end, Set<String> dict){ if (start == null || end == null || start.equals(end) || start.length() != end.length()) return 0; if (isOneWordDiff(start, end)) return 2; Queue<String> queue=new LinkedList<String>(); HashMap<String,Integer> dist=new HashMap<String,Integer>(); queue.add(start); dist.put(start, 1); while(!queue.isEmpty()) { String head=queue.poll(); int headDist=dist.get(head); //从每一个位置开始替换成a~z for(int i=0;i<head.length();i++) { for(char j='a';j<'z';j++) { if(head.charAt(i)==j) continue; char[] s = head.toCharArray(); s[i]=j; String sb = new String(s); if(sb.toString().equals(end)) return headDist+1; if(dict.contains(sb.toString())&&!dist.containsKey(sb.toString())) { queue.add(sb.toString()); dist.put(sb.toString(), headDist+1); } } } } return 0; } private boolean isOneWordDiff(String a, String b) { int diff = 0; for (int i = 0; i < a.length(); i++) { if (a.charAt(i) != b.charAt(i)) { diff++; if (diff >= 2) return false; } } return diff == 1; }
相关推荐
public void helper(TreeNode root, int level){// 当前层没有 list,新建// 取得当前层的 list迭代pub
java lru leetcode leetcode-algorithms-java leetcode 算法笔记-java
java lru leetcode LeetCode-Tag-Java 解决方案 LeetCode 的解决方案 指数
力扣解题java版本
https://github.com/geekxingyun/leetcode-java-algorithm-solution.git 然后你会发现当前项目有两个模块。 完成:它是完成的项目,并有一些关于 leetcode 的答案。 初始:只需在模块项目中编写代码 如果您不知道...
leetcode Leetcode-Java-解决方案 Java 中 Leetcode 问题的解决方案
用Java实现基础数据结构,排序算法、经典算法以及leetcode刷题记录_Java_下载.zip
LeetCode-Python-Java zhouzhenping/LeetCode-Python&Java 参考代码来源 力扣(LeetCode) 链接: 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。 Github 01 两数之和 给定一个整数数组 ...
#Leetcode-In-Java 代码并不全是本人写的,有的参考了网络上其他前辈的想法,但都能在OJ上AC。 ###索引 1 . Two-Sum 要点: - 利用java中Array对象的sort方法排序,使得整个数组呈升序状态 - 再利用两段取点...
leetcode 答案LeetCode-答案-Java 我的 leetcode 用伪代码和分析用 java 回答
然后通过用循环来解:假设第一个for循环是一个数组的循环,而后它的内嵌循环是也是这个数组,只是下标从0变成了1,这样,在第一次循环时,第1个元素会与其他所有元素
LeetCode题解 - Java语言实现-181页.pdf
分类LeetCode-Java-接受 这是 Leetcode 问题的 Java 解决方案。 细节 标题和答案格式 /* * 17. Letter Combinations of a Phone Number * Target: Given a string containing digits from 2-9 inclusive, return all...
示例解题思路最大的深度是左子树或右子树中深度中更大的一个+1,递归的在子树的子树中寻找代码实现Definition for a binary tree node
Answer-Java 数组 11.乘最多水容器 maxArea 26.删除排序数组中的重复项 removeDuplicates 33.搜索旋转排序数组 search 34.在排序数组中查找元素的第一个和最后一个位置 searchRange 48.旋转图像 rotate 54.螺旋矩阵 ...
LeetCode-Practice-Java leetcode 练习题 这个项目就是自己练习leetCode的实际Demo 有些公司就会问一些算法问题,即便是不问的话自己不学这块感觉也对不起自己的职业。。。 所以自己在学习的时候 也打算把优秀的答案...
leetcode 答案Leetcode-Java - 符合条件(Hacktoberfest) JAVA 中的 Leetcode 答案
leetcode-for-Java Record the process of leetcode for Java. 引言 记录一下,在leetcode上刷题的过程。 前期以刷题为主。有空的话就更新一下这个目录,然后顺带把有写问题的解题思路写上。 目录
leetcode 100 4-Leetcode 进入后直接搜索题号即可 001 - 100 题号 题目 考点 001 【Hash Table】 005 【动态规划】 007 【栈】 【纯数学】 053 【分治】 【动态规划】 062 【简单动态规划 】 【纯数学】 094 【中序...
leetcode-cli-plugins leetcode-cli 的第 3 方插件。 什么是 如何使用 如何使用 插件 名称 描述 增强的命令 按公司或标签过滤问题 list 不要在同一台计算机上使 Chrome 的会话过期 login 不要在同一台计算机上使 ...