Word Ladder II

Given two words (start and end), and a dictionary, find all shortest transformation sequence(s) from start to end, such that:

1. Only one letter can be changed at a time
2. 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"]
     ]
   

   Note:
   

   • All words have the same length.
   • All words contain only lowercase alphabetic characters. 这个题目着实用了不少时间,中间做了两个取巧的处理:

     1.把end放到dict里面这样的好处就是在BFS建立图的时候 可以直接获取end的前继,所有.这样可以减少最后处理的麻烦

     2.把dfs中处理进行优化,可以直接处理到当前继没有的时候,这个时候最后一个节点一定是start

     3.中间建立一个MAP map中保存不同的str对应的前继

     4.如果一个串被发现了,那么要看一下是不是distance和之前的str差一个,这个是为了保证不出现绕环

     5.对str的每一位做变换,使时间复杂度下来.而刚开始的时候是比较有一个位不相同,但是对海量的处理的时候反而会降低速度.

     6.对最后结果要把新的放在0位，oneAnswer.add(0,end).因为是从后往前扫

     
     

     public class Solution {
     	public ArrayList
           
            > findLadders(String start,
     			String end, HashSet
            
              dict) { dict.add(end); ArrayList
             
              > result = new ArrayList
              
               >(); if (start == null || end == null || start.length() != end.length()) { return result; } Map
               
                 map = new HashMap
                
                 (); Queue
                 
                   queue = new LinkedList
                  
                   (); queue.offer(start); map.put(start, new MyNode(start, 1)); while (!queue.isEmpty()) { String cur = queue.poll(); if (reachEnd(cur, end)) { outputResult(end, new ArrayList
                   
                    (), map, result); return result; } for (int i = 0; i < cur.length(); i++) { for (char c = 'a'; c <= 'z'; c++) { String changeStr = getOneDiff(cur, i, c); if (dict.contains(changeStr)) { MyNode curNode = map.get(cur); int curDist = curNode.distance; int newDist = curDist + 1; if (!map.containsKey(changeStr)) { MyNode newNode = new MyNode(changeStr, newDist); newNode.pre.add(curNode); queue.offer(changeStr); map.put(changeStr, newNode); } else { MyNode preNode = map.get(changeStr); int preDist = preNode.distance; if (newDist == preDist) { preNode.pre.add(curNode); } } } } } } return result; } private void outputResult(String end, ArrayList
                    
                      oneAnswer, Map
                     
                       map, ArrayList
                      
                       > result) { MyNode curNode = map.get(end); oneAnswer.add(0, end); if (curNode.pre.isEmpty()) { result.add(new ArrayList
                       
                        (oneAnswer)); return; } for (MyNode eachNode : curNode.pre) { outputResult(eachNode.val, oneAnswer, map, result); oneAnswer.remove(0); } } private void getPaths(MyNode myNode, Map
                        
                          map, ArrayList
                         
                           curPath, ArrayList
                          
                           > paths) { if (myNode == null) { paths.add(curPath); return; } curPath.add(0, myNode.val); if (!myNode.pre.isEmpty()) { for (MyNode prevNode : myNode.pre) { getPaths(prevNode, map, new ArrayList
                           
                            (curPath), paths); } } else { getPaths(null, map, curPath, paths); } } boolean reachEnd(String left, String right) { if (left.equals(right)) { return true; } return false; } String getOneDiff(String str, int pos, char c) { StringBuffer sb = new StringBuffer(str); sb.setCharAt(pos, c); return sb.toString(); } } class MyNode { String val; int distance; LinkedList
                            
                              pre; MyNode(String v, int distance) { this.val = v; this.distance = distance; pre = new LinkedList
                             
                              (); } void addPre(MyNode p) { pre.add(p); } }
                             
                            
                           
                          
                         
                        
                       
                      
                     
                    
                   
                  
                 
                
               
              
             
            
           

     
     
     

     
     

     不得不说,这个题做的确实痛苦,但是做AC了之后感觉很爽!

     也不知道各位大神有什么更好的办法,反正我做的时候确实感觉到很挑战,但很有意思.

     过瘾!