# Question

Formatted question description: https://leetcode.ca/all/126.html

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.


Constraints:

• 1 <= beginWord.length <= 5
• endWord.length == beginWord.length
• 1 <= wordList.length <= 500
• wordList[i].length == beginWord.length
• beginWord, endWord, and wordList[i] consist of lowercase English letters.
• beginWord != endWord
• All the words in wordList are unique.
• The sum of all shortest transformation sequences does not exceed 105.

# Algorithm

This solution uses a combination of Breadth-First Search (BFS) for discovering the shortest paths and Depth-First Search (DFS) for building the actual paths, a common approach for such problems.

Here’s a step-by-step explanation of the code:

### BFS Phase

1. Initialization: The words set contains all the words from wordList, ensuring quick lookup. If endWord is not in words, the function returns an empty list as no transformation is possible.

2. Distance and Predecessor Tracking: dist keeps track of the shortest distance (in terms of steps) from beginWord to any word encountered during BFS. prev is a mapping from a word to all of its predecessors on the shortest path from the beginWord.

3. BFS Execution: Starting from beginWord, the code iteratively transforms each letter of the current word to all possible 26 letters and checks if the new word is in words. If a new valid word is found, it’s added to the queue for further exploration, and its distance and predecessors are updated. The BFS continues until endWord is found (found = True), ensuring only the shortest paths are considered.

4. Key BFS Details:

• The BFS layer-by-layer processing is essential for finding the shortest path efficiently.
• When a transformation leads to a word already at the current step, it means this word can be reached through another transformation, so the current word is added as its predecessor.
• The check if dist.get(t, 0) == step ensures that only words reachable in the current number of steps are considered, which helps in identifying all predecessors of words on the shortest paths.
• Once endWord is found, the BFS search can stop, as all shortest paths to endWord would have been discovered due to the layer-by-layer nature of BFS.

### DFS Phase

1. Building Paths: The dfs function is a recursive function that constructs paths from endWord back to beginWord using the prev mapping filled during BFS. It does so by starting with endWord and recursively exploring all its predecessors, appending each valid path to ans.

2. Path Construction: The path is constructed in reverse (from endWord to beginWord) because the prev mapping stores how to reach each word from the start word, making it natural to traverse the mapping in reverse to reconstruct the path. Once the path reaches beginWord, it’s reversed to match the required direction and added to ans.

3. Efficiency Considerations: The reason for traversing from endWord to beginWord (as noted in the comment) is to reduce the number of paths explored during DFS. Since prev contains only predecessors on the shortest paths, paths that do not lead to endWord in the minimum number of steps are naturally excluded, making the DFS phase more efficient.

### Conclusion

This approach ensures that all shortest transformation sequences are found by first using BFS to discover the shortest path lengths and record predecessors, then using DFS to build the paths from these predecessors. The combination of BFS for shortest path discovery and DFS for path construction is a powerful pattern for solving similar problems in graph theory and word transformation challenges.

# Code

• import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Queue;
import java.util.Set;

// iteration bfs
public class Solution {

List<List<String>> list = new ArrayList<List<String>>();

public List<List<String>> findLadders(String start, String end, Set<String> dict) {

if (start == null || end == null || dict == null) return list;

int level = 1;
int currentLevelCount = 1;
int newLevelCount = 0;
boolean found = false;
int foundLevel = -1;

// from end word, to all paths
HashMap<String, ArrayList<ArrayList<String>>> hm = new HashMap<String, ArrayList<ArrayList<String>>>();

q.offer(start);
ArrayList<String> singlePath = new ArrayList<String>();
ArrayList<ArrayList<String>> allPaths = new ArrayList<ArrayList<String>>();

hm.put(start, allPaths);

while (!q.isEmpty()) {

String current = q.poll();
currentLevelCount--; // 这里用了新旧count来标记每个level，没有用null

for (int i = 0; i < current.length(); i++) {
char[] array = current.toCharArray();

for (char c = 'a'; c <= 'z'; c++) {
array[i] = c;
String each = new String(array);
if (each.equals(end)) {
found = true;
foundLevel = level;
}

if (dict.contains(each)) {
// q.offer(each);
newLevelCount++;

ArrayList<ArrayList<String>> prevAllPaths = hm.get(current);

if (hm.containsKey(each))
allPaths = hm.get(each);
else {
/* @note@note:
enqueue is here. if no path ending at this one, then has to explore in future
if there is path ending at this one, meaning it's been explored already. no need to enqueue
*/
q.offer(each);
allPaths = new ArrayList<ArrayList<String>>();
hm.put(each, allPaths);
}

// @note@note: this if is the key !!! no path for new word, or new word path is one more than previous path
// using this if, the"if visited" check can be removed
// if (allPaths.size() == 0 || prevAllPaths.size() + 1 == allPaths.size()) {
if (allPaths.size() == 0 || prevAllPaths.get(0).size() + 1 == allPaths.get(0).size()) {
for (ArrayList<String> eachPath : prevAllPaths) {
ArrayList<String> newone = new ArrayList<String>(eachPath);
}
}
}
}
}

// @note@note: also the key, to make sure only find shortest
if (found && foundLevel != level) {
break;
}

// @note: must be after trying the last word of currentLevel, then update
if (currentLevelCount == 0) {
currentLevelCount = newLevelCount;
newLevelCount = 0;
level++;

}

}

if (!found) {
return list;
}

for (ArrayList<String> each : hm.get(end)) {
}

return list;

}
}

public class Solution_recursion {

private List<String> findPath(String fromWord, String toWord,
Set<String> seenWords) {

if (fromWord.equals(toWord)) {
ArrayList<String> result = new ArrayList<>();
return result;
}

// Find all words that you can go to from fromWord
List<String> nextWords = getNextWords(fromWord, seenWords);
for (String word : nextWords) {
Set<String> newSeenWords = new HashSet<String>(seenWords);
List<String> subPath = findPath(word, toWord, newSeenWords);
if (subPath != null) {
return subPath;
}
}

// There wasn't a path
return null;

}

private final List<String> WORDS = Arrays.asList("head", "heal",
"teal", "tell", "tall", "tail");

private final List<Character> ALPHA = Arrays.asList('a', 'b',
'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n',
'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z');

private final HashSet<String> DICTIONARY = new HashSet<String>(
WORDS);

private List<String> getNextWords(String fromWord,
Set<String> seenWords) {
List<String> outList = new ArrayList<String>();
StringBuilder builder;
for (int i = 0; i < fromWord.length(); i++) {
builder = new StringBuilder(fromWord);
for (Character j : ALPHA) {
if (j == fromWord.charAt(i)) {
continue;
}
builder.setCharAt(i, j);
String potentialWord = builder.toString();
if (DICTIONARY.contains(potentialWord)
&& !seenWords.contains(potentialWord)) {
}
}
}
return outList;
}
}
}

//////

class Solution {
private List<List<String>> ans;
private Map<String, Set<String>> prev;

public List<List<String>> findLadders(String beginWord, String endWord, List<String> wordList) {
ans = new ArrayList<>();
Set<String> words = new HashSet<>(wordList);
if (!words.contains(endWord)) {
return ans;
}
words.remove(beginWord);
Map<String, Integer> dist = new HashMap<>();
dist.put(beginWord, 0);
prev = new HashMap<>();
Queue<String> q = new ArrayDeque<>();
q.offer(beginWord);
boolean found = false;
int step = 0;
while (!q.isEmpty() && !found) {
++step;
for (int i = q.size(); i > 0; --i) {
String p = q.poll();
char[] chars = p.toCharArray();
for (int j = 0; j < chars.length; ++j) {
char ch = chars[j];
for (char k = 'a'; k <= 'z'; ++k) {
chars[j] = k;
String t = new String(chars);
if (dist.getOrDefault(t, 0) == step) {
}
if (!words.contains(t)) {
continue;
}
words.remove(t);
q.offer(t);
dist.put(t, step);
if (endWord.equals(t)) {
found = true;
}
}
chars[j] = ch;
}
}
}
if (found) {
Deque<String> path = new ArrayDeque<>();
dfs(path, beginWord, endWord);
}
return ans;
}

private void dfs(Deque<String> path, String beginWord, String cur) {
if (cur.equals(beginWord)) {
return;
}
for (String precursor : prev.get(cur)) {
dfs(path, beginWord, precursor);
path.removeFirst();
}
}
}

• '''

>>> a = set([11,22,33])
>>> a.remove(22)
>>> a
{33, 11}

>>> a = set([11,22,33])
>>> a
{33, 11}

>>> a=set([1,2,3])
>>> a.remove(555)
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
KeyError: 555
'''

class Solution:
self, beginWord: str, endWord: str, wordList: List[str]
) -> List[List[str]]:
# endWord to beginWord
# better than begin to end, too many paths not in final result
def dfs(path, cur):
if cur == beginWord:
ans.append(path[::-1])
return
for precursor in prev[cur]:
path.append(precursor)
dfs(path, precursor)
path.pop()

ans = []
words = set(wordList)
if endWord not in words:
return ans
# no exception if beginWord not in set
dist = {beginWord: 0}
prev = defaultdict(set)
q = deque([beginWord])
found = False
step = 0
step += 1
for _ in range(len(q), 0, -1):
p = q.popleft()
s = list(p)
for i in range(len(s)):
ch = s[i]
for j in range(26):
s[i] = chr(ord('a') + j)
t = ''.join(s)
if dist.get(t, 0) == step:
prev[t].add(p) # repeated 3 lines below
if t not in words:
# if above '== step' met, then t must be removed from words[] from previous iterations
continue
prev[t].add(p) # repeated 3 lines above
q.append(t)
dist[t] = step
if endWord == t:
found = True
s[i] = ch
if found:
path = [endWord]
dfs(path, endWord)
return ans

############

from collections import deque

class Solution(object):
"""
:type beginWord: str
:type endWord: str
:type wordlist: Set[str]
:rtype: List[List[int]]
"""

def getNbrs(src, dest, wordList):
res = []
for c in string.ascii_lowercase:
for i in range(0, len(src)):
newWord = src[:i] + c + src[i + 1:]
if newWord == src:
continue
if newWord in wordList or newWord == dest:
yield newWord

def bfs(beginWord, endWord, wordList):
distance = {beginWord: 0}
queue = deque([beginWord])
length = 0
while queue:
length += 1
for k in range(0, len(queue)):
top = queue.popleft()
for nbr in getNbrs(top, endWord, wordList):
if nbr not in distance:
distance[nbr] = distance[top] + 1
queue.append(nbr)
return distance

def dfs(beginWord, endWord, wordList, path, res, distance):
if beginWord == endWord:
res.append(path + [])
return

for nbr in getNbrs(beginWord, endWord, wordList):
if distance.get(nbr, -2) + 1 == distance[beginWord]:
path.append(nbr)
dfs(nbr, endWord, wordList, path, res, distance)
path.pop()

res = []
distance = bfs(endWord, beginWord, wordlist)
dfs(beginWord, endWord, wordlist, [beginWord], res, distance)
return res


• func findLadders(beginWord string, endWord string, wordList []string) [][]string {
var ans [][]string
words := make(map[string]bool)
for _, word := range wordList {
words[word] = true
}
if !words[endWord] {
return ans
}
words[beginWord] = false
dist := map[string]int{beginWord: 0}
prev := map[string]map[string]bool{}
q := []string{beginWord}
found := false
step := 0
for len(q) > 0 && !found {
step++
for i := len(q); i > 0; i-- {
p := q[0]
q = q[1:]
chars := []byte(p)
for j := 0; j < len(chars); j++ {
ch := chars[j]
for k := 'a'; k <= 'z'; k++ {
chars[j] = byte(k)
t := string(chars)
if v, ok := dist[t]; ok {
if v == step {
prev[t][p] = true
}
}
if !words[t] {
continue
}
if len(prev[t]) == 0 {
prev[t] = make(map[string]bool)
}
prev[t][p] = true
words[t] = false
q = append(q, t)
dist[t] = step
if endWord == t {
found = true
}
}
chars[j] = ch
}
}
}
var dfs func(path []string, begin, cur string)
dfs = func(path []string, begin, cur string) {
if cur == beginWord {
cp := make([]string, len(path))
copy(cp, path)
ans = append(ans, cp)
return
}
for k := range prev[cur] {
path = append([]string{k}, path...)
dfs(path, beginWord, k)
path = path[1:]
}
}
if found {
path := []string{endWord}
dfs(path, beginWord, endWord)
}
return ans
}