### LeetCode  • ㊗️
• 大家
• offer
• 多多！

## 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<>();

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.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
// 如果之前没有到达过这个单词, 需要添加最短距离
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)) {
}
}
}

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) {

if (end.equals(cur)) {
} 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