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