126 Word Ladder II
126. Word Ladder II
1. Question
Given two words (beginWord and endWord), and a dictionary's word list, find all shortest transformation sequence(s) from beginWord to endWord, such that:
Only one letter can be changed at a time
Each transformed word must exist in the word list. Note that
beginWord is not a transformed word.
For example,
Given:
beginWord="hit"
endWord="cog"
wordList=["hot","dot","dog","lot","log","cog"]
Return
[
["hit","hot","dot","dog","cog"],
["hit","hot","lot","log","cog"]
]
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.
2. Implementation
(1) BFS + Backtracking
思路:
(1)利用BFS找到最短路径,和每个word的邻近的word
(2) 通过回溯法,找出所有的路径
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
BFS + Backtracking: 时间复杂度? , 空间复杂度?
Last updated
Was this helpful?