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.

class Solution {
    public List<List<String>> findLadders(String beginWord, String endWord, List<String> wordList) {
        List<List<String>> res = new ArrayList<>();
        Queue<List<String>> queue = new LinkedList<>();
        Set<String> dict = new HashSet<>(wordList);
        Set<String> visited = new HashSet<>(Arrays.asList(beginWord));
        queue.offer(Arrays.asList(beginWord));
        // Last round will be toggled when we hit one one of the shortest path
        boolean lastRound = false;
        while (!queue.isEmpty() && !lastRound) {
            Set<String> nextVisited = new HashSet<>(visited);
            for (int i = queue.size(); i > 0; i--) {
                List<String> curList = queue.poll();

                String curW = curList.get(curList.size() - 1);
                if (curW.equals(endWord)) {
                    res.add(curList);
                    lastRound = true;
                    continue;
                }
                for (int j = 0; j < curW.length(); j++) {
                    char[] next = curW.toCharArray();
                    for (char k = 'a'; k <= 'z'; k++) {
                        if (next[j] == k)
                            continue;
                        next[j] = k;
                        String cand = String.valueOf(next);
                        if (dict.contains(cand) && !visited.contains(cand)) {
                            List<String> candList = new ArrayList<>(curList);
                            nextVisited.add(cand);
                            candList.add(cand);
                            queue.offer(candList);
                        }
                    }
                }
            }
            visited = nextVisited;
        }
        return res;
    }
}