Leetcode 126 Word Ladder II

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

1. Only one letter can be changed at a time
2. Each intermediate word must exist in the word list

For example,

Given:
beginWord = "hit"
endWord = "cog"
wordList = ["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.

Solution 1: The assumption is that the dictionary is huge and word itself is short, so we can not search the wordList, but change the each letter at one time then look up if it exist in the dictionary. The algorithm is to use BFS to build a graph, then do DFS to get the whole list. Use set to track each level of the ladder (like queue in BFS).

 public class Solution {  
   public List<List<String>> findLadders(String beginWord, String endWord, Set<String> wordList) {  
     Map<String,List<String>> map=new HashMap<>();  
     Set<String> set=new HashSet<>();  
     set.add(beginWord);  
     boolean found=false;  
     while (!found && !set.isEmpty()) {  
       wordList.removeAll(set);  
       Set<String> nextSet=new HashSet<>();  
       for (String s:set) {  
         List<String> adj=new ArrayList<>();  
         char[] c=s.toCharArray();  
         for (int i=0; i<c.length; i++) {  
           char temp=c[i];  
           for (char r='a'; r<='z'; r++) {  
             c[i]=r;  
             String x=new String(c);  
             if (x.equals(endWord)) {  
               found=true;  
               adj.add(x);  
             }  
             else if (wordList.contains(x)) {  
               adj.add(x);  
               nextSet.add(x);  
             }  
           }  
           c[i]=temp;  
         }  
         map.put(s,adj);  
       }  
       set=nextSet;  
     }  
     List<List<String>> res=new ArrayList<>();  
     List<String> one=new ArrayList<>();  
     dfs(map,beginWord,endWord,one,res);  
     return res;  
   }  
   private void dfs(Map<String,List<String>> map, String s, String endWord, List<String> one, List<List<String>> res) {  
     one.add(s);  
     if (s.equals(endWord)) res.add(new ArrayList<String>(one));  
     else if (map.containsKey(s)) {  
       for (String x:map.get(s)) dfs(map,x,endWord,one,res);  
     }  
     one.remove(one.size()-1);  
   }  
 }  

Solution 2: Optimize use 2 sets and search from both begin and end. Use the smaller set to perform next step. Run time 36 ms.

 public class Solution {  
   public List<List<String>> findLadders(String beginWord, String endWord, Set<String> wordList) {  
     Set<String> set1=new HashSet<>();  
     Set<String> set2=new HashSet<>();  
     Map<String,List<String>> map=new HashMap<>();  
     set1.add(beginWord);  
     set2.add(endWord);  
     boolean dir=true, found=false;  
     while (!found && !set1.isEmpty() && !set2.isEmpty()) { //set can not be empty, otherwise in dead loop  
       if (set1.size()>set2.size()) {  
         Set<String> temp=set1;  
         set1=set2;  
         set2=temp;  
         dir=!dir;  
       }  
       wordList.removeAll(set1);  
       Set<String> nextSet=new HashSet<>();  
       for (String word: set1) {  
         char c[]=word.toCharArray();  
         for (int i=0; i<c.length; i++) {  
           char org=c[i];  
           for (char r='a'; r<='z'; r++) {  
             c[i]=r;  
             String s=new String(c);  
             if (set2.contains(s) || wordList.contains(s)) {  
               if (set2.contains(s)) found=true;  
               String key=dir?word:s;  
               String value=dir?s:word;  
               if (map.containsKey(key)) map.get(key).add(value);  
               else {  
                 List<String> list=new LinkedList<>();  
                 list.add(value);  
                 map.put(key,list);  
               }  
               nextSet.add(s);  
             }  
           }  
           c[i]=org;  
         }  
       }  
       set1=nextSet;  
     }  
     List<String> one=new ArrayList<>();  
     List<List<String>> res=new ArrayList<>();  
     dfs(map,beginWord,endWord,one,res);  
     return res;  
   }  
   private void dfs(Map<String,List<String>> map, String word, String endWord, List<String> one, List<List<String>> res) {  
     one.add(word);  
     if (word.equals(endWord)) res.add(new ArrayList<String>(one));  
     else if (map.containsKey(word)) { // pay attention here  
       for (String s: map.get(word)) dfs(map,s,endWord,one,res);  
     }  
     one.remove(one.size()-1);  
   }  
 }