Word Ladder

WordLadder.java

/**
 * Given two words (start and end), and a dictionary, find the length of shortest transformation sequence 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"]
 * As one shortest transformation is "hit" -> "hot" -> "dot" -> "dog" -> "cog",
 * return its length 5.
 * Note:
 * Return 0 if there is no such transformation sequence.
 * All words have the same length.
 * All words contain only lowercase alphabetic characters.
 */

public class Solution {
    public int ladderLength(String start, String end, HashSet<String> dict) {
        int res = 0;
        if(dict.size() == 0) 
            return res;
        dict.add(start);
        dict.add(end);
        res = BFS(start, end, dict);
        return res;
    }
    private int BFS(String start, String end, HashSet<String> dict) {
        Queue<String> queue = new LinkedList<String>();
        Queue<Integer> length = new LinkedList<Integer>();
        queue.offer(start);
        length.offer(1);
        while(!queue.isEmpty()) {
            String word = queue.poll();
            int len = length.poll();
            if(word.equals(end))
                return len;
            for(int i = 0; i < word.length(); i++) {
                char[] arr = word.toCharArray();
                for(char c = 'a'; c <= 'z'; c++) {
                    if(c == arr[i])
                        continue;
                    arr[i] = c;
                    String str = String.valueOf(arr);
                    if(dict.contains(str)) {
                        queue.add(str);
                        length.add(len + 1);
                        dict.remove(str);
                    }
                }
            }
        }
        return 0;
    }
}

WordLadderII.java

/**
 * Given two words (start and end), and a dictionary, find the length of shortest transformation sequence 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:
 * Return 0 if there is no such transformation sequence.
 * All words have the same length.
 * All words contain only lowercase alphabetic characters.
 */

public class Solution {
    public ArrayList<ArrayList<String>> findLadders(String start, String end, HashSet<String> dict) {
        HashMap<String, HashSet<String>> visited = new HashMap<String, HashSet<String>>();
        HashMap<String, Integer> level = new HashMap<String, Integer>();
        LinkedList<String> queue = new LinkedList<String>();
        ArrayList<ArrayList<String>> res = new ArrayList<ArrayList<String>>();
        if(start == null || end == null || start.length() != end.length())
            return res;
        HashSet<String> path = new HashSet<String>();
        int minLen = Integer.MAX_VALUE;
        visited.put(start, path); // only difference from word letter I
        level.put(start, 1);
        queue.add(start);
        while(!queue.isEmpty()) {
            String head = queue.poll();
            char[] chars = head.toCharArray();
            for(int i = 0; i < head.length(); i++) {
                char old = chars[i];
                for(char letter = 'a'; letter <= 'z'; letter++) {
                    chars[i] = letter;
                    String nextWord = new String(chars);
                    // two possible situations
                    // level does not contain nextWord
                    // level contains nextWord and near the start
                    if(dict.contains(nextWord) && (!level.containsKey(nextWord) || (level.containsKey(nextWord) && level.get(nextWord) > level.get(head)))) {
                        // we update the path, visited, level
                        if(visited.containsKey(nextWord)) {
                            visited.get(nextWord).add(head);
                        } else {
                            path = new HashSet<String>();
                            path.add(head);
                            visited.put(nextWord, path);
                            level.put(nextWord, level.get(head) + 1);
                            queue.offer(nextWord);
                        }
                    }
                    if(nextWord.equals(end)) {
                        if(level.get(head) < minLen) {
                            ArrayList<String> entry = new ArrayList<String>();
                            entry.add(end);
                            res.addAll(backtrace(head, visited, entry));
                            minLen = level.get(head) + 1;
                        } else {
                            break;
                        }
                    }
                    chars[i] = old;
                }
            }
        }
        return res;
    }
    private ArrayList<ArrayList<String>> backtrace(String end, HashMap<String, HashSet<String>> visited, ArrayList<String> path) {
        ArrayList<ArrayList<String>> res = new ArrayList<ArrayList<String>>();
        ArrayList<String> entry = new ArrayList<String>(path);
        entry.add(0, end);
        if (visited.get(end).size() < 1) {
            res.add(entry);
            return res;
        }
        for(String str : visited.get(end)) {
            res.addAll(backtrace(str, visited, entry));
        }
        return res;
    }
}

WordLadderII_2BFS.java

public class Solution {
    /**
     * This is a solution with 2-way BFS
     */
    public List<List<String>> findLadders(String start, String end, Set<String> dict) {
        // Hash set for both ends
        Set<String> set1 = new HashSet<String>();
        Set<String> set2 = new HashSet<String>();
        
        // Initial words in both ends
        set1.add(start);
        set2.add(end);
        
        // We use a map to help construct the final result
        Map<String, List<String>> map = new HashMap<String, List<String>>();
        
        // build the map
        helper(dict, set1, set2, map, false);
        
        List<List<String>> res = new ArrayList<List<String>>();
        List<String> sol = new ArrayList<String>(Arrays.asList(start));
        
        // recursively build the final result
        generateList(start, end, map, sol, res);
        return res;
    }
    
    
    
    public boolean helper(Set<String> dict, Set<String> set1, Set<String> set2, Map<String, List<String>> map, boolean flip) {
        if(set1.isEmpty()) return false;
        if(set1.size() > set2.size()) return helper(dict, set2, set1, map, !flip);
        
        // remove words on current both ends from the dict
        dict.removeAll(set1);
        dict.removeAll(set2);
        
        // as we only need the shortest paths
        // we use a boolean value to help teminate early
        boolean done = false;
        
        // set for the next level
        Set<String> set = new HashSet<String>();
        
        // for each String in end 1
        for(String str : set1) {
            for(int i = 0; i < str.length; i++) {
                char[] chars = str.toCharArray();
                
                // change one character for every position
                for(char ch = 'a'; ch <= 'z'; ch++) {
                    chars[i] = ch;
                    String word = new String(chars);
                    
                    // make sure we construct the tree in the correct direction
                    String key = flip ? word : str;
                    String val = flip ? str : word;
                    
                    List<String> list = map.containsKey(key) ? map.get(key) : new ArrayList<String>();
                    if(set2.contains(word)){
                        done = true;
                        list.add(val);
                        map.put(key, list);
                    }
                    
                    if(!done && dict.contains(word)) {
                        set.add(word);
                        list.add(val);
                        map.put(key, list);
                    }
                }
            }
        }
        // terminate early if done
        return done || helper(dict, set2, set, map, !flip);
    }
    
    private void generateList(String start, String end, Map<String, List<String>> map, List<String> sol, List<List<String>> res) {
        if(start.equals(end)) {
            res.add(new ArrayList<String>(sol));
            return;
        }
        
        // need this check in case the diff between start and end happens to be one
        // e.g. "a", "c", {"a", "b", "c"}
        if(!map.containsKey(start))  return;
        for(String word : map.get(start)) {
            sol.add(word);
            generateList(word, end, map, sol, res);
            sol.remove(sol.size() - 1);
        }
    }
}