126. Word Ladder II

126. Word Ladder II

Given two words (beginWord and endWord), and a dictionary's word list, find all shortest transformation sequence(s) from beginWord to endWord, such that:

1. Only one letter can be changed at a time
2. Each transformed word must exist in the word list. Note that beginWord is not a transformed word.

Note:

• Return an empty list if there is no such transformation sequence.
• All words have the same length.
• All words contain only lowercase alphabetic characters.
• You may assume no duplicates in the word list.
• You may assume beginWord and endWord are non-empty and are not the same.

Example 1:

Input:
beginWord = "hit",
endWord = "cog",
wordList = ["hot","dot","dog","lot","log","cog"]

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

Example 2:

Input:
beginWord = "hit"
endWord = "cog"
wordList = ["hot","dot","dog","lot","log"]

Output: []

Explanation: The endWord "cog" is not in wordList, therefore no possible transformation.

-----------------
在I上做了一些修改，每个Pair都会记录当前走过的点

class Solution {
    public List<List<String>> findLadders(String beginWord, String endWord, List<String> wordList) {
        int n = beginWord.length();
        Map<String, Integer> dic = getDic(wordList);
        dic.put(beginWord, 1);
        Queue<Pair> que = new LinkedList<>();
        List<String> ll = new ArrayList<>();
        ll.add(beginWord);
        que.add(new Pair(1, beginWord, ll));
        List<List<String>> rt = new ArrayList<>();
        
        while (!que.isEmpty()) {
            Pair p = que.poll();
            String cur = p.s;
            
            if (!rt.isEmpty() && p.level > rt.get(0).size()) {
                return rt;
            }
            if (cur.equals(endWord)) {
                rt.add(p.list);
                continue;
            }
            
            for (int i = 0; i < n; i++) {
                char c = cur.charAt(i);
                for (char nextC = 'a'; nextC <= 'z'; nextC++) {
                    String next = cur.substring(0, i) + nextC + cur.substring(i + 1);
                    
                    // Note: ">=", as we want to output all possible paths.
                    if (dic.containsKey(next) && dic.get(next) >= p.level + 1) { 
                        List<String> l = new ArrayList<>(p.list);
                        l.add(next);
                        que.add(new Pair(p.level + 1, next, l));
                        dic.put(next, p.level + 1);
                    }
                }
            }
        }
        
        return rt;
    }
    
    private Map<String, Integer> getDic(List<String> wordList) {
        Map<String, Integer> dic = new HashMap<>();
        
        for (String s : wordList) {
            dic.put(s, Integer.MAX_VALUE);
        }
        
        return dic;
    }
    
    class Pair{
        public int level;
        public String s;
        public List<String> list;
        public Pair(int level, String s, List<String> list) {
            this.level = level;
            this.s = s;
            this.list = list;
        }
    }
}