## Algorithm

Problem Name: 126. Word Ladder II

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

## Code Examples

### #1 Code Example with C Programming

```Code - C Programming```

``````
typedef struct {
int idx;
char *s;
int *p;
int psz;
int pn;
} node_t;
typedef struct {
node_t **q;
int n;
} q_t;
typedef struct {
char ***p;
int psz;
int pn;
int d;
} res_t;
void add2res(res_t *res, char **buff, int l) {
int sz = l * sizeof(char *);
char **p = malloc(sz);
//assert(p);
memcpy(p, buff, sz);

if (res->psz == res->pn) {
res->psz = !res->psz ? 10 : res->psz * 2;
res->p = realloc(res->p, res->psz * sizeof(char **));
//assert(res->p);
}
res->p[res->pn ++] = p;
}
int one_diff(char *a, char *b) {
int diff = 0;
while (*a && diff  < = 1) {
diff += (*a != *b) ? 1 : 0;
a ++; b ++;
}
return diff == 1 ? 1 : 0;
}
void add2prev(node_t *b, int idx) {
if (b->psz == b->pn) {
b->psz = !b->psz ? 5 : b->psz * 2;
b->p = realloc(b->p, b->psz * sizeof(int));
//assert(b->p);
}
b->p[b->pn ++] = idx;
}
void bt(node_t *nodes, node_t *n, char **buff, res_t *res, int l, int d) {
int i;

if (n->idx == -1) {  // done
buff[d] = n->s;
return;
}
buff[d] = n->s;
for (i = 0; i  <  n->pn; i ++) {
bt(nodes, &nodes[n->p[i]], buff, res, l, d - 1);
}
}
void bfs(q_t *q1, q_t *q2, node_t *nodes, int sz, char *end, int *visited, res_t *res) {
node_t *done, *a, *b;
q_t *q3;
int d = 1, i;

char **buff;

done = NULL;
while (q1->n && !done) {
while (q1->n) {
a = q1->q[-- q1->n];
for (i = 0; i  <  sz; i ++) {
if (visited[i] > 1) continue;
b = &nodes[i];
if (one_diff(a->s, b->s)) {
if (!done && !strcmp(b->s, end)) done = b;
if (!visited[i]) {
q2->q[q2->n ++] = b;
visited[i] = 1;     // 1 means it is just added into q2
}
}
}
}
for (i = 0; !done && i  <  q2->n; i ++) {
b = q2->q[i];
visited[b->idx] ++;  // done for this layer, make them all 2
}
q3 = q1;
q1 = q2;
q2 = q3;
d ++;
}

if (!done) return;

res->d = d;

// backtrace done node to make buff
buff = malloc(d * sizeof(char *));
//assert(buff);

bt(nodes, done, buff, res, d, d - 1);

free(buff);
}
char*** findLadders(char* beginWord, char* endWord, char** wordList, int wordListSize, int** columnSizes, int* returnSize) {
int *visited, i;
node_t *n, *nodes;
q_t q1 = { 0 }, q2 = { 0 };
res_t res = { 0 };

visited = calloc(wordListSize, sizeof(int));
nodes = malloc((wordListSize + 1) * sizeof(node_t));
q1.q = malloc(wordListSize * 2 * sizeof(node_t *));
//assert(visited && nodes && q1.q);
q2.q = &q1.q[wordListSize];

n = &nodes[0];
n->idx = -1;
n->s = beginWord;
for (i = 0; i  <  wordListSize; i ++) {
n = &nodes[i + 1];
n->idx = i;
n->s = wordList[i];
n->p = NULL;
n->psz = 0;
n->pn = 0;
}

q1.q[q1.n ++] = &nodes[0];

bfs(&q1, &q2, &nodes[1], wordListSize, endWord, visited, &res);

free(visited);
free(q1.q);
for (i = 1; i  < = wordListSize; i ++) {
n = &nodes[i];
if (n->p) free(n->p);
}
free(nodes);

if (res.pn) {
*columnSizes = malloc(res.pn * sizeof(int));
//assert(*columnSizes);
}
for (i = 0; i  <  res.pn; i ++) {
(*columnSizes)[i] = res.d;
}

*returnSize = res.pn;

return res.p;
}
``````
Copy The Code &

Input

cmd
beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log","cog"]

Output

cmd
[["hit","hot","dot","dog","cog"],["hit","hot","lot","log","cog"]]

### #2 Code Example with Javascript Programming

```Code - Javascript Programming```

``````
const findLadders = function (beginWord, endWord, wordList) {
const res = []
if (!wordList.includes(endWord)) return res
const set1 = new Set([beginWord]),
set2 = new Set([endWord]),
wordSet = new Set(wordList),
temp = [beginWord]
const map = new Map()
const traverse = (set1, set2, dir) => {
if (set1.size === 0) return false
if (set1.size > set2.size) return traverse(set2, set1, !dir)
for (const val of set1.values()) {
if (wordSet.has(val)) wordSet.delete(val)
}
for (const val of set2.values()) {
if (wordSet.has(val)) wordSet.delete(val)
}
const set = new Set()
let done = false
for (const str of set1.values()) {
for (let i = 0; i  <  str.length; i++) {
for (let ch = 'a'.charCodeAt(); ch  < = 'z'.charCodeAt(); ch++) {
const word =
str.slice(0, i) + String.fromCharCode(ch) + str.slice(i + 1)
const key = dir ? str : word
const val = dir ? word : str
const list = map.get(key) || []
if (set2.has(word)) {
done = true
list.push(val)
map.set(key, list)
}
if (!done && wordSet.has(word)) {
list.push(val)
map.set(key, list)
}
}
}
}
return done || traverse(set2, set, !dir)
}
const dfs = (word) => {
if (word === endWord) {
res.push(temp.slice())
return
}
const nei = map.get(word) || []
for (const w of nei) {
temp.push(w)
dfs(w)
temp.pop()
}
}
traverse(set1, set2, true)
dfs(beginWord)
return res
}
``````
Copy The Code &

Input

cmd
beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log","cog"]

Output

cmd
[["hit","hot","dot","dog","cog"],["hit","hot","lot","log","cog"]]

### #3 Code Example with Python Programming

```Code - Python Programming```

``````
class Solution:
words, res, layer = set(wordList), [], {beginWord: [[beginWord]]}
while layer:
newlayer = collections.defaultdict(list)
for w in layer:
if w == endWord:
for arr in layer[w]:
res.append(arr)
else:
for i in range(len(w)):
for c in string.ascii_lowercase:
neww = w[:i] + c + w[i + 1:]
if neww in words:
newlayer[neww] += [j + [neww] for j in layer[w]]
words -= set(newlayer.keys())
layer = newlayer
return res
``````
Copy The Code &

Input

cmd
beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log"]

Output

cmd
[]

### #4 Code Example with C# Programming

```Code - C# Programming```

``````
using System.Collections.Generic;

namespace LeetCode
{
{
public IList < IList wordList)
{
var map = new HashSet(wordList);
if (!map.Contains(endWord))
return new List() { beginWord });

}

private void FindLadders(string beginWord, string endWord, IDictionary < string, HashSet solution)
{
if (beginWord == endWord)
{
return;
}

if (!graph.ContainsKey(beginWord)) return;

foreach (var word in graph[beginWord])
{
solution.RemoveAt(solution.Count - 1);
}
}

private bool BuildGraph(string beginWord, string endWord, HashSet < string> wordList, IDictionary();
var used2 = new HashSet();

var done = false;
var backward = false;

while (used1.Count != 0 && used2.Count != 0 && !done)
{
if (used1.Count > used2.Count)
{
var temp = used1;
used1 = used2;
used2 = temp;
backward = !backward;
}

foreach (string word in used1)
wordList.Remove(word);
foreach (string word in used2)
wordList.Remove(word);

var current_used = new HashSet < string>();

foreach (string word in used1)
{
char[] charArray = word.ToCharArray();
for (int j = 0; j  <  wordLength; j++)
{
var temp = charArray[j];
for (char ch = 'a'; ch  < = 'z'; ch++)
{
charArray[j] = ch;
var nextWord = new string(charArray);

string parent = backward ? nextWord : word;
string child = backward ? word : nextWord;

if (used2.Contains(nextWord))
{
done = true;
if (!graph.ContainsKey(parent)) graph.Add(parent, new HashSet < string>());
}

if (wordList.Contains(nextWord) && !done)
{
if (!graph.ContainsKey(parent)) graph.Add(parent, new HashSet < string>());
}
}
charArray[j] = temp;
}
}
used1 = current_used;
}

return done;
}
}
}
``````
Copy The Code &

Input

cmd
beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log"]

Output

cmd
[]