【leetcode】String——Word Ladder II（126）

题目：

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

Only one letter can be changed at a timeEach intermediate word must exist in the word list

For example,

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

思路：BFS backtrace

先用BFS，每次只改变一个字母，找到从start到end的最短路径，就拿题目中的例子来说。很类似Dijisktra。

第一步：hit -> hot

第二步：hot -> dot   或   hot -> lot 

第三步：dot -> dog  或   lot ->log 

第四步：dog -> cog 或 log ->cog

在BFS中用map记录路径：{cog=[dog, log], lot=[hot], hot=[hit], dog=[dot], log=[lot], dot=[hot]}

在用backtrace，从end找start

代码：代码参考了leetcode大神：https://discuss.leetcode.com/topic/2857/share-two-similar-java-solution-that-accpted-by-oj

public class Word_Ladder_II_bfs { Map<String,List<String>> map; List<List<String>> results; public List<List<String>> findLadders(String start, String end, Set<String> dict) { results= new ArrayList<List<String>>(); if (dict.size() == 0) return results; int min=Integer.MAX_VALUE; dict.add(end); Queue<String> queue= new ArrayDeque<String>(); queue.add(start); map = new HashMap<String,List<String>>(); Map<String,Integer> ladder = new HashMap<String,Integer>(); for (String string:dict) ladder.put(string, Integer.MAX_VALUE); ladder.put(start, 0); dict.add(end); //BFS: Dijisktra search while (!queue.isEmpty()) { String word = queue.poll(); int step = ladder.get(word)+1;//'step' indicates how many steps are needed to travel to one word. if (step>min) break; for (int i = 0; i < word.length(); i++){ StringBuilder builder = new StringBuilder(word); for (char ch='a'; ch <= 'z'; ch++){ builder.setCharAt(i,ch); String new_word=builder.toString(); if (ladder.containsKey(new_word)) { if (step>ladder.get(new_word))//Check if it is the shortest path to one word. continue; else if (step<ladder.get(new_word)){ queue.add(new_word); ladder.put(new_word, step); }else;// It is a KEY line. If one word already appeared in one ladder, // Do not insert the same word inside the queue twice. Otherwise it gets TLE. if (map.containsKey(new_word)) //Build adjacent Graph map.get(new_word).add(word); else{ List<String> list= new LinkedList<String>(); list.add(word); map.put(new_word,list); //It is possible to write three lines in one: //map.put(new_word,new LinkedList<String>(Arrays.asList(new String[]{word}))); //Which one is better? } if (new_word.equals(end)) min=step; }//End if dict contains new_word }//End:Iteration from 'a' to 'z' }//End:Iteration from the first to the last }//End While //BackTracking LinkedList<String> result = new LinkedList<String>(); backTrace(end,start,result); return results; } private void backTrace(String word,String start,List<String> list){ if (word.equals(start)){ list.add(0,start); results.add(new ArrayList<String>(list)); list.remove(0); return; } list.add(0,word); if (map.get(word)!=null) for (String s:map.get(word)) backTrace(s,start,list); list.remove(0); } }