ID | Title | Difficulty | |
---|---|---|---|
Loading... |
126. Word Ladder II
Hard
LeetCode
Hash Table, String, Backtracking, Breadth-First Search
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.
Code
class Solution {
public List<List<String>> findLadders(String start, String end, List<String> wordList) {
List<List<String>> res = new ArrayList<>();
HashSet<String> dict = new HashSet<>(wordList);
HashMap<String, ArrayList<String>> neigh = new HashMap<>();
HashMap<String, Integer> distance = new HashMap<>();
dict.add(start);
build(start, end, dict, neigh, distance);
search(start, end, neigh, distance, new ArrayList<>(), res);
return res;
}
private void build(
String start,
String end,
Set<String> dict,
HashMap<String, ArrayList<String>> neigh,
HashMap<String, Integer> distance) {
for (String str : dict) {
neigh.put(str, new ArrayList<>());
}
Queue<String> queue = new LinkedList<>();
queue.offer(start);
distance.put(start, 0);
while (!queue.isEmpty()) {
int size = queue.size();
// 是否找到目标单词
boolean found = false;
// current level
for (int i = 0; i < size; i++) {
String cur = queue.poll();
// 到当前这个单词的最短距离
int curDistance = distance.get(cur);
// 得到可以由当前词转化成的词
ArrayList<String> neighbors = getNeighbors(cur, dict);
for (String neighbor : neighbors) {
// 添加neighbor
neigh.get(cur).add(neighbor);
// 如果之前没有到达过这个单词, 需要添加最短距离
if (!distance.containsKey(neighbor)) {
distance.put(neighbor, curDistance + 1);
// 找到目标单词, 但是仍然要继续完成本层遍历
// 因为有可能有多条路径
if (end.equals(neighbor)) {
found = true;
} else {
queue.offer(neighbor);
}
}
}
}
if (found) break;
}
}
// Find all next level nodes.
private ArrayList<String> getNeighbors(String word, Set<String> dict) {
ArrayList<String> res = new ArrayList<>();
for (int i = 0; i < word.length(); i++) {
StringBuilder sb = new StringBuilder(word);
for (char ch = 'a'; ch <= 'z'; ch++) {
sb.setCharAt(i, ch);
String newWord = sb.toString();
// neighbor必须在dict中才是合法的
if (dict.contains(newWord)) {
res.add(newWord);
}
}
}
return res;
}
private void search(
String cur,
String end,
HashMap<String, ArrayList<String>> neigh,
HashMap<String, Integer> distance,
ArrayList<String> temp,
List<List<String>> res) {
temp.add(cur);
if (end.equals(cur)) {
res.add(new ArrayList<>(temp));
} else {
for (String next : neigh.get(cur)) {
// 下一个单词是最短距离到达的
if (distance.get(next) == distance.get(cur) + 1) {
search(next, end, neigh, distance, temp, res);
}
}
}
// 需要去掉本层的单词
temp.remove(temp.size() - 1);
}
}
- Time: O(N * (26 ^ L)), L = len(word), N = len(wordList)
- Space: O(N + K * P), K = number of paths, P = path length
按 <- 键看上一题!
125. Valid Palindrome
按 -> 键看下一题!
127. Word Ladder