[LeetCode] 126. Word Ladder II

摘要：存放过程中的所有集合为所有的结尾，则顺序存放这个结尾对应的中的所有存放同一个循环的新加入的，在下一个循环再依次对其中元素进行进一步的把首个字符串放入新，再将放入，并将键值对放入，进行初始化

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

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

Given:

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

Return

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

class Solution {
    public List> findLadders(String start, String end, List wordList) {
        List> res = new ArrayList<>();
        Set dict = new HashSet<>(wordList);
        if (!dict.contains(end)) return res;
        //save shortest distance from start to each node
        Map distanceMap = new HashMap<>();
        //save all the nodes can be transformed from each node
        Map> neighborMap = new HashMap<>();
        
        dict.add(start);
        //use bfs to: find the shortest distance; update neighborMap and distanceMap
        bfs(start, end, dict, neighborMap, distanceMap);
        //use dfs to: output all the paths with the shortest distance
        dfs(start, end, neighborMap, distanceMap, new ArrayList<>(), res);
        
        return res;
    }
    
    private void bfs(String start, String end, Set dict, Map> neighborMap, Map distanceMap) {
        for (String str: dict) {
            neighborMap.put(str, new ArrayList<>());
        }
        
        Deque queue = new ArrayDeque<>();
        queue.offer(start);
        distanceMap.put(start, 0);
        
        while (!queue.isEmpty()) {
            int size = queue.size();
            boolean foundEnd = false;
            for (int i = 0; i < size; i++) {
                String cur = queue.poll();
                int curDist = distanceMap.get(cur);
                List neighbors = getNeighbors(dict, cur);
                
                for (String neighbor: neighbors) {
                    neighborMap.get(cur).add(neighbor);
                    if (!distanceMap.containsKey(neighbor)) {
                        distanceMap.put(neighbor, curDist+1);
                        if (neighbor.equals(end)) foundEnd = true;
                        else queue.offer(neighbor);
                    }
                }
            }
            if (foundEnd) break;
        }
    }
    
    private void dfs(String start, String end, Map> neighborMap, Map distanceMap, List temp, List> res) {
        if (start.equals(end)) {
            temp.add(start);
            res.add(new ArrayList<>(temp));
            temp.remove(temp.size()-1);
        }
        for (String neighbor: neighborMap.get(start)) {
            temp.add(start);
            if (distanceMap.get(neighbor) == distanceMap.get(start)+1) {
                dfs(neighbor, end, neighborMap, distanceMap, temp, res);
            }
            temp.remove(temp.size()-1);
        }
    }
    
    private List getNeighbors(Set dict, String str) {
        List res = new ArrayList<>();
        for (int i = 0; i < str.length(); i++) {
            StringBuilder sb = new StringBuilder(str);
            for (char ch = "a"; ch <= "z"; ch++) {
                sb.setCharAt(i, ch);
                String neighbor = sb.toString();
                if (dict.contains(neighbor)) res.add(neighbor);
            }
        }
        return res;
    }
}

result: 存放transformation过程中的所有List集合

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

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

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

public class Solution {
    public List> findLadders(String start, String end, Set dict) {
        List> res = new ArrayList<>();
        List preList = new ArrayList<>();
        Queue queue = new LinkedList<>();
        Map>> 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> temp = new ArrayList<>();
                        for (List p: map.get(pre)) {
                            List 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>();
    }
}