Given two words (startandend), and a dictionary, find all shortest transformation sequence(s) fromstarttoend, such that:

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

Notice

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

Have you met this question in a real interview?

Yes

Example

Given:
start="hit"
end="cog"
dict=["hot","dot","dog","lot","log"]

Return

  [
    ["hit","hot","dot","dog","cog"],
    ["hit","hot","lot","log","cog"]
  ]

1. DFS + BFS

so we need to get 'all possible' solution. we need a dfs here, but we also need only the shortest path. so bfs can help us with this.

and as we setting off from the start and moving towards the end, the way that we have to choose the path has to be decided by the distance from the next point to the end. we will move there only if the distance to the end reduced not stay the same or increased. so the basic bfs as if in the word ladder I, and we need to bfs from the end to the start and remembers the SHORTEST distance from every point (so only remember the first time it is visited on the bfs) . then dfs based on the distance from start to end.

 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 (dict == null || dict.size() == 0) {
            return ans;
        }

        dict.add(start);
        dict.add(end);

        //bfs from the end to the start to calculate the distance from each point to the end
        HashMap<String, Integer> disToEnd = bfsDistanceToEnd(start, end, dict);

        List<String> cur = new ArrayList<>();
        //dfs from start to end
        int distance = disToEnd.get(start);
        dfsFindLadders(ans, cur, distance ,disToEnd, start, end, dict);

        return ans;
    }

    public void dfsFindLadders(List<List<String>> ans, 
                               List<String> cur, 
                               int distance,
                               HashMap<String, Integer> disToEnd, 
                               String start, 
                               String end, 
                               Set<String> dict) {

        //exit
        cur.add(start);

        if (start.equals(end)) {
            ans.add(new ArrayList<String>(cur));
            return;
        }



        //拆解
        for (String next : getNextWordList(dict, start)) {
            if (disToEnd.get(next) >= distance) {
                continue;
            }
            dfsFindLadders(ans, cur, disToEnd.get(next), disToEnd, next, end, dict);
            cur.remove(cur.size() - 1);
        }

    }


    public HashMap<String, Integer> bfsDistanceToEnd(String start, String end, Set<String> dict) {
        HashMap<String, Integer> ans = new HashMap<>();

        Queue<String> queue = new LinkedList<>();
        queue.offer(end);
        ans.put(end, 0);

        int count = 0;
        while (!queue.isEmpty()) {
            int size = queue.size();
            count++;
            for (int i = 0; i < size; i++) {
                String cur = queue.poll();
                for (String next : getNextWordList(dict, cur)) {
                    if (ans.containsKey(next)) {
                        continue;
                    }
                    if (next.equals(start)) {
                        ans.put(start, count);
                        continue;
                    }
                    queue.offer(next);
                    ans.put(next, count);
                }
            }
        }
        return ans;
    }


    public ArrayList<String> getNextWordList(Set<String> dict, String word) {
        ArrayList<String> ans = new ArrayList<>();
        for (int i = 0; i < word.length(); i++) {
            for (char j = 'a'; j < 'z'; j++) {
                if (j == word.charAt(i)) {
                    continue;
                }

                String newString = replace(word, i, j);
                if (dict.contains(newString)) {
                    ans.add(newString);
                }
            }
        }
        return ans;
    }

    public String replace(String word, int index, char x) {
        char[] chars = word.toCharArray();
        chars[index] = x;
        return new String(chars);
    }


}