Problem: A transformation sequence from word beginWord to word endWord using a dictionary wordList is a sequence of words beginWord -> s1 -> s2 -> ... -> sk such that:

• Every adjacent pair of words differs by a single letter.

• Every si for 1 <= i <= k is in wordList. Note that beginWord does not need to be in wordList.

• sk == endWord

Given two words, beginWord and endWord, and a dictionary wordList, return all the shortest transformation sequences from beginWord to endWord, or an empty list if no such sequence exists. Each sequence should be returned as a list of the words [beginWord, s1, s2, ..., sk].

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"]]

Explanation: There are 2 shortest transformation sequences:

"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 there is no valid transformation sequence.

Constraints:

• 1 <= beginWord.length <= 5

• endWord.length == beginWord.length

• 1 <= wordList.length <= 500

• wordList[i].length == beginWord.length

• beginWord, endWord, and wordList[i] consist of lowercase English letters.

• beginWord != endWord

• All the words in wordList are unique.

• The sum of all shortest transformation sequences does not exceed 105.

 

class Solution {

    public List<List<String>> findLadders(String beginWord, String endWord, List<String> wordList) {

        List<List<String>> results = new ArrayList<List<String>>();

        var q = new LinkedList<String>();

        var s = new HashSet<String>(wordList);

        q.add(beginWord);

        var result = new ArrayList<String>();

        combine(beginWord, endWord, s, results, result);

        var minOpt = results.stream().filter(x -> x.get(0).equals(beginWord)).mapToInt(x -> x.size()).min();

        if (minOpt.isPresent()) {

            var min = minOpt.getAsInt();

            results = results.stream().filter(x -> x.size() == min).collect(Collectors.toList());

        }

        return results;

    }

    private static void combine(String top, String endWord, HashSet<String> s, List<List<String>> results, List<String> result)

    {

            if (top.equals(endWord)) {

                return;

            }

            result.add(top);

            char[] chars = top.toCharArray();

            for (int i = 0; i < chars.length; i++)

            {

                for (char c = 'a'; c <= 'z'; c++)

                {

                    char temp = chars[i];

                    if (temp != c) {

                        chars[i] = c;

                    }

                    String candidate = new String(chars);

                    if (s.contains(candidate) && !result.contains(candidate)) {

                        var clone = new ArrayList<String>(result);

                        if (candidate.equals(endWord)) {

                            clone.add(candidate);

                            results.add(clone);

                        } else {

                            combine(candidate, endWord, s, results, clone);

                        }

                    }

                    chars[i] = temp;

                }

            }

            result.remove(top);

    }

}

 

Test cases:

1.

Input

beginWord =

"hit"

endWord =

"cog"

wordList =

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

Output

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

Expected

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

2.

Input

beginWord =

"hit"

endWord =

"cog"

wordList =

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

Output

[]

Expected

[]