# Word Ladder II Double BFS

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].

```
from collections import defaultdict
class Solution:
def findLadders(self, beginWord: str, endWord: str, wordList: List[str]) -> List[List[str]]:
# edge case
if endWord not in wordList:
return []
# 1) build neighbor list for first bfs
if beginWord not in wordList:
wordList.append(beginWord)
unseen = set(wordList)
word_size = len(beginWord)
neighbors = defaultdict(list)
for word in wordList:
for i in range(word_size):
neighbors[f'{word[:i]}*{word[i+1:]}'].append(word)
# 2) do first bfs and build reversed neighbors list for second bfs
reverse_neighbors = defaultdict(list)
n_t_h = [beginWord]
unseen.remove(beginWord)
while n_t_h:
new_seen = set()
for word in n_t_h:
for i in range(word_size):
for neighbor in neighbors[f'{word[:i]}*{word[i+1:]}']:
if neighbor in unseen:
reverse_neighbors[neighbor].append(word)
new_seen.add(neighbor)
n_t_h = list(new_seen)
unseen -= new_seen
if reverse_neighbors[endWord]:
break
# if endWord does not have reversed neigbors it is not reachable so return empty list
if not reverse_neighbors[endWord]:
return []
# 3) do second bfs
paths = [[endWord]]
while True:
new_paths = []
for path in paths:
last_node = path[-1]
for reverse_neighbor in reverse_neighbors[last_node]:
new_paths.append(path + [reverse_neighbor])
paths = new_paths
if paths[0][-1] == beginWord:
break
# 4) reverse the paths
result = []
for path in paths:
path.reverse()
result.append(path)
return result
```

## Related Problems

There is an integer array nums sorted in ascending order (with **distinct** values).

Prior to being passed to your function, nums is **possibly rotated** at an unknown pivot index k (1 <= k < nums.length) such that the resulting array is [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]] (**0-indexed**). For example, [0,1,2,4,5,6,7] might be rotated at pivot index 3 and become [4,5,6,7,0,1,2].

Given the array nums **after** the possible rotation and an integer target, return *the index of *target* if it is in *nums*, or *-1* if it is not in *nums.

You must write an algorithm with O(log n) runtime complexity.

Given an array of **distinct** integers candidates and a target integer target, return *a list of all ***unique combinations*** of *candidates* where the chosen numbers sum to *target*.* You may return the combinations in **any order**.

The **same** number may be chosen from candidates an **unlimited number of times**. Two combinations are unique if the frequency of at least one of the chosen numbers is different.

There are a total of numCourses courses you have to take, labeled from 0 to numCourses - 1. You are given an array prerequisites where prerequisites[i] = [ai, bi] indicates that you **must** take course bi first if you want to take course ai.

For example, the pair [0, 1], indicates that to take course 0 you have to first take course 1.

Return true if you can finish all courses. Otherwise, return false.

Given an array nums of n integers where nums[i] is in the range [1, n], return *an array of all the integers in the range* [1, n] *that do not appear in* nums.