Leetcode Word Ladder II 解题报告

发布时间:2017-5-30 20:59:53 编辑:www.fx114.net 分享查询网我要评论
本篇文章主要介绍了"Leetcode Word Ladder II 解题报告",主要涉及到Leetcode Word Ladder II 解题报告方面的内容,对于Leetcode Word Ladder II 解题报告感兴趣的同学可以参考一下。

http://oj.leetcode.com/problems/word-ladder-ii/ Given two words (start and end), and a dictionary, find all shortest transformation sequence(s) from start to end, such that: Only one letter can be changed at a time Each intermediate word must exist in the dictionary For example, Given: start = "hit" end = "cog" dict = ["hot","dot","dog","lot","log"] Return   [     ["hit","hot","dot","dog","cog"],     ["hit","hot","lot","log","cog"]   ] 题意说明:从start变换到end,途中只能经过字典中的单词,每次只允许差一个字母。 要求输出所有变换路径。 分析:题倒是不难,但时间卡的特别紧。 常规方法:BFS搜索,节点的数据结构包含:当前单词、记录变换路径的hash表、记录变换路径的ArrayList。搜索所有和当前单词只差一个字母的单词,查询新单词是否在字典中同时是否已经存在于变换路径中,如果在字典中同时不在已有的变换路径中,把新单词放入队列,继续BFS。代码如下,可惜大数据超时。 class Pair { String str; ArrayList<String> path; HashSet<String> hash; Pair(String str, ArrayList<String> path, HashSet<String> hash) { this.str = str; this.path = path; this.hash = hash; } } public class Solution { public ArrayList<ArrayList<String>> findLadders(String start, String end, HashSet<String> dict) { ArrayList<ArrayList<String>> result = new ArrayList<ArrayList<String>>(); ArrayList<String> path = new ArrayList<String>(); HashSet<String> hash = new HashSet<String>(); if(start==null||end==null||start.length()!=end.length()) { return result; } Queue queue = new LinkedList<Pair>(); path.add(start); hash.add(start); Pair node = new Pair(start, path,hash); int min_length = -1; queue.add(node); while(!queue.isEmpty()) { node = (Pair)queue.poll(); String str = node.str; for(int i=0;i<str.length();i++) { char[] strCharArr = str.toCharArray(); for(char ch='a';ch<='z';ch++) { if(strCharArr[i]==ch) { continue; } strCharArr[i] = ch; String newWord = new String(strCharArr); if(newWord.equals(end)==true) { path = node.path; path.add(newWord); if(min_length==-1) { min_length = path.size(); } if(path.size()>min_length) { return result; } else { result.add(path); //dict.remove(newWord); continue; } } else { if(dict.contains(newWord)&&!node.hash.contains(newWord)){ path = new ArrayList<String>(node.path); hash = new HashSet<String>(node.hash); path.add(newWord); hash.add(newWord); Pair newnode = new Pair(newWord, path,hash); queue.add(newnode); //dict.remove(newWord); } } } } } return result; } } 其实一般面试能写出上面的代码足以交差,但这道题貌似是Leetcode上面通过率最低的一道题,只能想办法优化了。 优化方法:先BFS生成找到end时的生成树,标记出每个单词所在的层数。然后从目标用DFS往回找,过了大数据。 AC代码: public class Solution { //记录每个单词所在的层数 HashMap<String,Integer> path = new HashMap<String,Integer>(); //bfs生成path void bfs(String start, String end, HashSet<String> dict) { Queue queue = new LinkedList<String>(); queue.add(start); path.put(start,0); String current; while(!queue.isEmpty()) { current = (String)queue.poll(); if(current==end) { continue; } for(int i=0;i<current.length();i++) { char[] strCharArr = current.toCharArray(); for(char ch='a';ch<='z';ch++) { if(strCharArr[i]==ch) { continue; } strCharArr[i] = ch; String newWord = new String(strCharArr); if(newWord.equals(end)==true||dict.contains(newWord)) { //每个单词在path中只能出现一次,也就是每个单词只能出现在一层中,这样就很巧妙的解决了环的问题。 if(path.get(newWord)==null) { int depth = (int)path.get(current); path.put(newWord,depth + 1); queue.add(newWord); } } } } } } //从目标单词往回找开始单词,记录所有路径 void dfs(String start, String end, HashSet<String> dict, ArrayList<String> pathArray,ArrayList<ArrayList<String>> result) { //找到了,需要reverse加入的所有单词 if(start.equals(end)==true) { pathArray.add(start); Collections.reverse(pathArray); result.add(pathArray); return; } if(path.get(start)==null) { return; } pathArray.add(start); int nextDepth = (int)path.get(start) - 1; for(int i=0;i<start.length();i++) { char[] strCharArr = start.toCharArray(); for(char ch='a';ch<='z';ch++) { if(strCharArr[i]==ch) { continue; } strCharArr[i] = ch; String newWord = new String(strCharArr); //只相差一个字母同时这个单词所在的层数也是当前单词的上一层 if(path.get(newWord)!=null&&(path.get(newWord)==nextDepth)) { ArrayList<String> newPathArray = new ArrayList<String>(pathArray); dfs(newWord,end,dict,newPathArray,result); } } } } public ArrayList<ArrayList<String>> findLadders(String start, String end, HashSet<String> dict) { ArrayList<ArrayList<String>> result = new ArrayList<ArrayList<String>>(); ArrayList<String> path = new ArrayList<String>(); if(start==null||end==null||start.length()!=end.length()) { return result; } bfs(start, end, dict); dfs(end,start, dict, path, result); return result; } }

上一篇:算法起步之拓扑排序
下一篇:代码究竟能写多长

相关文章

相关评论

本站评论功能暂时取消,后续此功能例行通知。

一、不得利用本站危害国家安全、泄露国家秘密,不得侵犯国家社会集体的和公民的合法权益,不得利用本站制作、复制和传播不法有害信息!

二、互相尊重,对自己的言论和行为负责。