Problem

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 time
Each intermediate word must exist in the dictionary

Notice

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

Example

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

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

Note

• result: 存放transformation过程中的所有List<String>集合

• map: key为所有transformation的结尾String，value则顺序存放这个结尾String对应的transformation中的所有String

• queue: 存放同一个循环level的新加入的String，在下一个循环再依次对其中元素进行进一步的BFS

• preList: 把首个字符串start放入新List，再将List放入res，并将start-res键值对放入map，进行初始化

Solution

public class Solution {
    public List<List<String>> findLadders(String start, String end, Set<String> dict) {
        List<List<String>> res = new ArrayList<>();
        List<String> preList = new ArrayList<>();
        Queue<String> queue = new LinkedList<>();
        Map<String, List<List<String>>> map = new HashMap<>();
        preList.add(start);
        queue.offer(start);
        res.add(preList);
        map.put(start, res);
        while (!queue.isEmpty()) {
            String pre = queue.poll();
            if (pre.equals(end)) return map.get(pre);
            for (int i = 0; i < pre.length(); i++) {
                for (int j = 0; j < 26; j++) {
                    StringBuilder sb = new StringBuilder(pre);
                    sb.setCharAt(i,(char) ('a'+j));
                    String cur = sb.toString();
                    if (!cur.equals(pre) && dict.contains(cur) && (!map.containsKey(cur) || map.get(pre).get(0).size()+1 <= map.get(cur).get(0).size())) {
                        List<List<String>> temp = new ArrayList<>();
                        for (List<String> p: map.get(pre)) {
                            List<String> curList = new ArrayList<>(p);
                            curList.add(cur);
                            temp.add(curList);
                        }
                        if (!map.containsKey(cur)) {
                            map.put(cur, temp);
                            queue.offer(cur);
                        }
                        else if (map.get(pre).get(0).size()+1 < map.get(cur).get(0).size()) map.put(cur, temp);
                        else map.get(cur).addAll(temp);
                        
                    }
                }
            }
        }
        return res.get(0).size() > 1 ? res : new ArrayList<List<String>>();
    }
}