Lintcode 121. Word Ladder II

Given two words (start and end), and a dictionary, find all shortest transformation sequence(s) from start to end, output sequence in dictionary order.
Transformation rule such that:

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

Example

Example 1:

Input：start = "a"，end = "c"，dict =["a","b","c"]
Output：[["a","c"]]
Explanation：
"a"->"c"

Example 2:

Input：start ="hit"，end = "cog"，dict =["hot","dot","dog","lot","log"]
Output：[["hit","hot","dot","dog","cog"],["hit","hot","lot","log","cog"]]
Explanation：
1."hit"->"hot"->"dot"->"dog"->"cog"
2."hit"->"hot"->"lot"->"log"->"cog"
The dictionary order of the first sequence is less than that of the second.

Notice

• All words have the same length.
• All words contain only lowercase alphabetic characters.

Solution:1. end -> start BFS, mark all distance2. start-> end, DFS, only go with the path with distance - 1

Code (Java):

public class Solution {
    /*
     * @param start: a string
     * @param end: a string
     * @param dict: a set of string
     * @return: a list of lists of string
     */
    public List<List<String>> findLadders(String start, String end, Set<String> dict) {
        // write your code here
        List<List<String>> ans = new ArrayList<>();
        if (start == null || start.length() == 0 || 
            end == null || end.length() == 0 || 
            dict == null || dict.size() == 0) {
            return ans;
        }
        
        // step 1: do a BFS from the end and mark the depth of each word
        Map<String, Integer> wordToDepthMap = new HashMap<>();
        int depth = 1;
        Queue<String> queue = new LinkedList<>();
        queue.offer(end);
        wordToDepthMap.put(end, depth);
        
        while (!queue.isEmpty()) {
            int size = queue.size();
            depth += 1;
            for (int i = 0; i < size; i++) {
                String curWord = queue.poll();
                char[] curWordChars = curWord.toCharArray();
                for (int j = 0; j < curWordChars.length; j++) {
                    char temp = curWordChars[j];
                    for (char c = 'a'; c <= 'z'; c++) {
                        if (c == temp) {
                            continue;
                        }
                        curWordChars[j] = c;
                        String nextWord = new String(curWordChars);
                        if ((dict.contains(nextWord) || nextWord.equals(start)) && !wordToDepthMap.containsKey(nextWord)) {
                            wordToDepthMap.put(nextWord, depth);
                            queue.offer(nextWord);
                        }
                    }
                    curWordChars[j] = temp;
                }
            }
        }
        
        for (String key : wordToDepthMap.keySet()) {
            int value = wordToDepthMap.get(key);
            System.out.println("key: " + key + " value: " + value);
        }
        
        // step 2 DFS of nodes with decreasing depth
        //
        List<String> curList = new ArrayList<>();
        curList.add(start);
        dfs(start, end, wordToDepthMap, curList, ans);
        
        return ans;
    }
    
    private void dfs(String curr, 
                     String end,
                     Map<String, Integer> wordToDepthMap, 
                     List<String> curList, 
                     List<List<String>> ans) {
        if (curr.equals(end)) {
            ans.add(new ArrayList<>(curList));
            return;
        }          
        
        char[] currChars = curr.toCharArray();
        for (int i = 0; i < currChars.length; i++) {
            char temp = currChars[i];
            for (char c = 'a'; c <= 'z'; c++) {
                if (c == temp) {
                    continue;
                }
                
                currChars[i] = c;
                String next = new String(currChars);
                if (wordToDepthMap.containsKey(next) && wordToDepthMap.get(next) == wordToDepthMap.get(curr) - 1) {
                    curList.add(next);
                    dfs(next, end, wordToDepthMap, curList, ans);
                    curList.remove(curList.size() - 1);
                }
            }
            currChars[i] = temp;
        }
    }
}