Given two words (beginWord and endWord), and a dictionary's word list, find all shortest transformation sequence(s) from beginWord to endWord, such that:
Copy [
["hit","hot","dot","dog","cog"],
["hit","hot","lot","log","cog"]
]
Copy class Solution {
public List<List<String>> findLadders(String beginWord, String endWord, List<String> wordList) {
List<List<String>> res = new ArrayList<>();
Set<String> dict = new HashSet<>(wordList);
Map<String, List<String>> neighbors = new HashMap<>();
Map<String, Integer> distance = new HashMap<>();
List<String> path = new ArrayList<>();
dict.add(beginWord);
getMinPathByBFS(beginWord, endWord, dict, neighbors, distance);
path.add(beginWord);
getAllPathsByDFS(beginWord, endWord, neighbors, distance, path, res);
return res;
}
public void getMinPathByBFS(String start, String end, Set<String> dict, Map<String, List<String>> neighbors, Map<String, Integer> distance) {
for (String word : dict) {
neighbors.put(word, new ArrayList<>());
}
Queue<String> queue = new LinkedList<>();
queue.add(start);
distance.put(start, 0);
boolean minLevel = false;
while (!queue.isEmpty() && !minLevel) {
int size = queue.size();
for (int i = 0; i < size; i++) {
String curWord = queue.remove();
int curDist = distance.get(curWord);
List<String> nextWords = getNeighbors(curWord, dict);
for (String nextWord : nextWords) {
neighbors.get(curWord).add(nextWord);
if (!distance.containsKey(nextWord)) {
distance.put(nextWord, curDist + 1);
if (nextWord.equals(end)) {
minLevel = true;
}
else {
queue.add(nextWord);
}
}
}
}
}
}
public List<String> getNeighbors(String word, Set<String> dict) {
List<String > res = new ArrayList<>();
char[] letters = word.toCharArray();
for (int i = 0; i < word.length(); i++) {
char oldC = letters[i];
for (char c = 'a'; c <= 'z'; c++) {
if (letters[i] == c) {
continue;
}
letters[i] = c;
String nextWord = new String(letters);
if (dict.contains(nextWord)) {
res.add(nextWord);
}
}
letters[i] = oldC;
}
return res;
}
public void getAllPathsByDFS(String start, String end, Map<String, List<String>> neighbors, Map<String, Integer> distance, List<String> path, List<List<String>> res) {
if (start.equals(end)) {
res.add(new ArrayList<String>(path));
return;
}
for (String neighbor : neighbors.get(start)) {
if (distance.get(neighbor) == distance.get(start) + 1) {
path.add(neighbor);
getAllPathsByDFS(neighbor, end, neighbors, distance, path, res);
path.remove(path.size() - 1);
}
}
}
}
3. Time & Space Complexity