0126. Word Ladder II
https://leetcode.com/problems/word-ladder-ii
Description
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
sifor1 <= i <= kis inwordList. Note thatbeginWorddoes not need to be inwordList.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 <= 5endWord.length == beginWord.length1 <= wordList.length <= 1000wordList[i].length == beginWord.lengthbeginWord,endWord, andwordList[i]consist of lowercase English letters.beginWord != endWordAll the words in
wordListare unique.
ac
class Solution {
// BFS build a directed Graph, better start from endWord, use map to circumvent loop
// DFS find paths
public List<List<String>> findLadders(String beginWord, String endWord, List<String> wordList) {
List<List<String>> res = new ArrayList<List<String>>(); // return result
// build the graph
Map<String, List<String>> graph = new HashMap<String, List<String>>(); // the graph
Map<String, Integer> visitedMap = new HashMap<String, Integer>(); // put visited node and it's layer
Set<String> wordSet = new HashSet<String>(wordList); // check whether dict contains word
if (!wordSet.contains(endWord)) return res;
wordSet.add(beginWord);
//BFS
Queue<String> q = new LinkedList<String>();
q.offer(endWord);
int layer = 0;
int shortest = Integer.MAX_VALUE; // stop BFS
while (!q.isEmpty()) {
layer++;
if (layer >= shortest) break; // shortest find, stop BFS
int len = q.size();
// layer by layer
for (int i = 0; i < len; i++) {
String start = q.poll();
char[] chars = start.toCharArray();
for (int k = 0; k < start.length(); k++) {
// construct new word
char old = chars[k];
for (char c = 'a'; c <= 'z'; c++) {
chars[k] = c;
String next = String.valueOf(chars);
// check new word in dict
if (wordSet.contains(next)) {
if (next == beginWord) shortest = layer + 1;
if (!visitedMap.containsKey(next)) {
// add to graph
List<String> tmpList = new ArrayList<String>();
tmpList.add(start);
graph.put(next, tmpList);
visitedMap.put(next, layer+1);
// add to queue for next
q.offer(next);
} else {
if (visitedMap.get(next) < layer + 1) {
continue; // loop, give up this word
} else {
graph.get(next).add(start); // add to graph
}
}
}
}
chars[k] = old;
}
}
}
List<String> tmpRes = new ArrayList<String>(); // tmp res note for DFS
if (!graph.containsKey(beginWord)) return res; // beginWord not even in the graph, return
dfs(graph, beginWord, endWord, tmpRes, res);
return res;
}
private void dfs(Map<String, List<String>> graph, String beginWord, String endWord, List<String> tmpRes, List<List<String>> res) {
tmpRes.add(beginWord);
if (beginWord.equals(endWord)) {
res.add(new ArrayList<String>(tmpRes));
tmpRes.remove(beginWord);
return;
}
for (String s : graph.get(beginWord)) {
// tmpRes.add(s);
dfs(graph, s, endWord, tmpRes, res);
// tmpRes.remove(s);
}
tmpRes.remove(beginWord);
}
}class Solution {
public List<List<String>> findLadders(String beginWord, String endWord, List<String> wordList) {
List<List<String>> res = new ArrayList<List<String>>();
Set<String> wordSet = new HashSet<String>(wordList);
// edge case
if (!wordSet.contains(endWord)) return res;
wordSet.add(beginWord);
wordSet.remove(endWord); // reverse
Map<String, List<String>> map = new HashMap<>(); // directed graph
Map<String, Integer> visited = new HashMap<>();
Queue<String> q = new LinkedList<>(); // BFS
q.offer(endWord);
int layer = 0;
boolean findShortest = false;
while (!q.isEmpty() && !findShortest) {
layer++;
int len = q.size();
for (int i = 0; i < len; i++) {
String h = q.poll();
char[] chars = h.toCharArray();
for (int j = 0; j < chars.length; j++) {
char old = chars[j];
for (char newChar = 'a'; newChar <= 'z'; newChar++) {
chars[j] = newChar;
String newWord = String.valueOf(chars);
if (wordSet.contains(newWord)) {
if (newWord.equals(beginWord)) findShortest = true;
if (!visited.containsKey(newWord)) {
map.put(newWord, new ArrayList<String>());
map.get(newWord).add(h);
q.offer(newWord);
visited.put(newWord, layer + 1);
} else {
if (visited.get(newWord) < layer + 1) continue; // visited in last layer, don't go back
map.get(newWord).add(h);
}
}
}
chars[j] = old;
}
}
}
// build Path
if (!map.containsKey(beginWord)) return res;
List<String> note = new ArrayList<String>();
note.add(beginWord);
dfs(map, beginWord, note, res);
return res;
}
private void dfs(Map<String, List<String>> map, String beginWord, List<String> note, List<List<String>> res) {
if (!map.containsKey(beginWord)) { // meet the end
res.add(new ArrayList<String>(note));
return;
}
for (String s : map.get(beginWord)) {
note.add(s);
dfs(map, s, note, res);
note.remove(note.size() - 1);
}
}
}
/*
build graph backwards
dfs get result
*/Last updated