Leetcode: Word Ladder II-白红宇

Leetcode: Word Ladder II

阅读量：5056 次

发布时间：2019-06-12

本文共 5314 字，大约阅读时间需要 17 分钟。

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"]  ]

Leetcode 里面通过概率最低的一道题，参看了别人的解法：利用bfs 层序遍历如果队列中有end 那么结束遍历（到最短的一层就结束）

1 import java.util.ArrayList;  2 import java.util.HashMap;  3 import java.util.HashSet;  4 import java.util.LinkedList;  5 import java.util.List;  6 import java.util.Map;  7 import java.util.Queue;  8 import java.util.Set;  9  10 public class Solution { 11     class WordWithLevel { 12         String word; 13         int level; 14  15         public WordWithLevel(String word, int level) { 16             this.word = word; 17             this.level = level; 18         } 19     } 20  21     private String end; 22     private ArrayList
     
      
       > result; 23     private Map
       
        > nextMap; 24  25     public ArrayList
        
         
          > findLadders(String start, String end, 26             HashSet
          
            dict) { 27 result = new ArrayList
           
            
             >(); 28 this.end = end; 29 30 // unvisited words set 31 Set
             
               unVisited = new HashSet
              
               (); 32 unVisited.addAll(dict); 33 unVisited.add(start); 34 unVisited.remove(end); 35 36 // used to record the map info of 
               
                 37 nextMap = new HashMap
                
                 >(); 38 for (String e : unVisited) { 39 nextMap.put(e, new ArrayList
                 
                  ()); 40 } 41 42 // BFS to search from the end to start 43 Queue
                  
                    queue = new LinkedList
                   
                    (); 44 queue.add(new WordWithLevel(end, 0)); 45 boolean found = false; 46 int finalLevel = Integer.MAX_VALUE; 47 int currentLevel = 0; 48 int preLevel = 0; 49 Set
                    
                      visitedWordsInThisLevel = new HashSet
                     
                      (); 50 while (!queue.isEmpty()) { 51 WordWithLevel wordWithLevel = queue.poll(); 52 String word = wordWithLevel.word; 53 currentLevel = wordWithLevel.level; 54 if (found && currentLevel > finalLevel) { 55 break; 56 } 57 if (currentLevel > preLevel) { 58 unVisited.removeAll(visitedWordsInThisLevel); 59 } 60 preLevel = currentLevel; 61 char[] wordCharArray = word.toCharArray(); 62 for (int i = 0; i < word.length(); ++i) { 63 char originalChar = wordCharArray[i]; 64 boolean foundInThisCycle = false; 65 for (char c = 'a'; c <= 'z'; ++c) { 66 wordCharArray[i] = c; 67 String newWord = new String(wordCharArray); 68 if (c != originalChar && unVisited.contains(newWord)) { 69 nextMap.get(newWord).add(word); 70 if (newWord.equals(start)) { 71 found = true; 72 finalLevel = currentLevel; 73 foundInThisCycle = true; 74 break; 75 } 76 if (visitedWordsInThisLevel.add(newWord)) { 77 queue.add(new WordWithLevel(newWord, 78 currentLevel + 1)); 79 } 80 } 81 } 82 if (foundInThisCycle) { 83 break; 84 } 85 wordCharArray[i] = originalChar; 86 } 87 } 88 89 if (found) { 90 // dfs to get the paths 91 ArrayList
                      
                        list = new ArrayList
                       
                        (); 92 list.add(start); 93 getPaths(start, list, finalLevel + 1); 94 } 95 return result; 96 } 97 98 private void getPaths(String currentWord, ArrayList
                        
                          list, int level) { 99 if (currentWord.equals(end)) {100 result.add(new ArrayList
                         
                          (list));101 } else if (level > 0) {102 List
                          
                            parentsSet = nextMap.get(currentWord);103 for (String parent : parentsSet) {104 list.add(parent);105 getPaths(parent, list, level - 1);106 list.remove(list.size() - 1);107 }108 }109 }110 }

自己的解法还需要多想想：

1 public class Solution { 2     public ArrayList
     
      
       > findLadders(String start, String end, Set
       
         dict) { 3         ArrayList
        
          Ladder=new ArrayList
         
          (); 4         ArrayList
          
           
            > LadderList=new ArrayList
            
             
              >(); 5 if(start.length() != end.length()) return LadderList; 6 shortestladders(start, end, dict, Ladder, LadderList); 7 return LadderList; 8 } 9 10 public void shortestladders(String start, String end, Set
              
                dict, ArrayList
               
                 Ladder, ArrayList
                
                 
                  > LadderList){11 Ladder.add(start);12 if(within(start, end)) { //end is only 1 bit different from start13 Ladder.add(end);14 if(LadderList.isEmpty()) { //LadderList is empty, so Ladder is definately shortest15 LadderList.add(Ladder);16 }17 else { //LadderList is not empty, so need comparition18 ArrayList
                  
                    shortestLadder = LadderList.get(0); // select one from LadderList19 if(Ladder.size() < shortestLadder.size()) { //new found Ladder is shorter than LadderList20 LadderList.clear();21 LadderList.add(Ladder);22 }23 else if(Ladder.size() == shortestLadder.size()) { //new found Ladder is the same with the LadderList,add to Ladderlist24 LadderList.add(Ladder);25 }26 // new found Ladder is longer than elems in LadderList, so do not change LadderList27 }28 Ladder.remove(Ladder.size()-1); //remove end29 }30 31 else { //end is more than 1 bit different from start, so look for temp elems in dict which is 1 bit different from start32 if(!dict.isEmpty()) {33 for(String temp:dict){34 if(within(start, temp)){35 dict.remove(start);36 shortestladders(temp, end, dict, Ladder, LadderList);37 dict.add(start);38 }39 }40 }41 42 }43 Ladder.remove(Ladder.size()-1); //remove start44 }45 46 public boolean within(String first, String second){47 int diff=0;48 for(int k=0; k