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 timeEach intermediate word must exist in the dictionaryFor 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生成pathvoid 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;}}
一个人身边的位置只有这么多，
