Algorithm

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 the number of words in the shortest transformation sequence from `beginWord` to `endWord`, or `0` if no such sequence exists.

Example 1:

```Input: beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log","cog"]
Output: 5
Explanation: One shortest transformation sequence is "hit" -> "hot" -> "dot" -> "dog" -> cog", which is 5 words long.
```

Example 2:

```Input: beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log"]
Output: 0
Explanation: The endWord "cog" is not in wordList, therefore there is no valid transformation sequence.
```

Constraints:

• `1 <= beginWord.length <= 10`
• `endWord.length == beginWord.length`
• `1 <= wordList.length <= 5000`
• `wordList[i].length == beginWord.length`
• `beginWord`, `endWord`, and `wordList[i]` consist of lowercase English letters.
• `beginWord != endWord`
• All the words in `wordList` are unique.

Code Examples

#1 Code Example with C Programming

```Code - C Programming```

``````
typedef struct {
char **q;
int n;
} q_t;
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;
}
int bfs(q_t *q1, q_t *q2, char *end, char **dict, int sz, int *v) {
int i, d;
char *a, *b;
q_t *tmp;

d = 1;
while (q1->n) {
while (q1->n) {
a = q1->q[-- q1->n];
for (i = 0; i  <  sz; i ++) {
if (v[i]) continue;
b = dict[i];
if (one_diff(a, b)) {
if (!strcmp(b, end)) {  // done!
return d;
}
v[i] = 1;
q2->q[q2->n ++] = b;
}
}
}
tmp = q1;  // switch queues
q1 = q2;
q2 = tmp;
d ++;
}

return -1;
}
int ladderLength(char* beginWord, char* endWord, char** wordList, int wordListSize) {
int *visited, i, n = 0;
q_t q1 = { 0 }, q2 = { 0 };

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

q1.q[q1.n ++] = beginWord;  // initialize q1

n = bfs(&q1, &q2, endWord, wordList, wordListSize, visited);

free(visited);
free(q1.q);

return n + 1;
}
``````
Copy The Code &

Input

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

Output

cmd
5

#2 Code Example with C++ Programming

```Code - C++ Programming```

``````
class Solution {
public:
int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
dequecur;
deque < string>next;
cur.push_back(beginWord);
int len = 2;
while(!cur.empty()){
string node = cur.front();
cur.pop_front();
for(auto& x: wordList){
if(x == "" || !isNeighbor(node, x)) continue;
if(x == endWord) return len;
next.push_back(x);
x = "";
}
if(cur.empty()){
len++;
swap(cur, next);
}
}
return 0;
}

bool isNeighbor(string& a, string& b){
int diff = 0;
for(int i = 0; i < a.size(); i++> if(a[i] != b[i] && ++diff > 1) return false;
return diff == 1;
}
};

// Two-end.
class Solution {
public:
int ladderLength(string beginWord, string endWord, vector < string>& wordList) {
if(find(wordList.begin(), wordList.end(), endWord) == wordList.end()) return 0;
unordered_setvisited0, visited1, *v0(&visited0), *v1(&visited1);
deque < string>cur0, next0, cur1, next1, *cur, *next;
cur0.push_back(beginWord);
cur1.push_back(endWord);
visited0.insert(beginWord);
visited1.insert(endWord);
int len = 2;
bool b = true;
while(!cur0.empty() && !cur1.empty()){
cur = b ? &cur0 : &cur1;
next = b ? &next0 : &next1;
string node = cur->front();
cur->pop_front();
for(auto& x: wordList){
if(v0->count(x) || !isNeighbor(node, x)) continue;
if(v1->count(x)) return len;
v0->insert(x);
next->push_back(x);
}
if(cur->empty()){
len++;
swap(*cur, *next);
swap(v0, v1);
b = !b;
}
}
return 0;
}

bool isNeighbor(string& a, string& b){
int diff = 0;
for(int i = 0; i < a.size(); i++> if(a[i] != b[i] && ++diff > 1) return false;
return diff == 1;
}
};
``````
Copy The Code &

Input

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

Output

cmd
5

#3 Code Example with Javascript Programming

```Code - Javascript Programming```

``````
const ladderLength = function(beginWord, endWord, wordList) {
const list = new Set(wordList)
if (!list.has(endWord)) return 0
let one = new Set([beginWord])
let two = new Set([endWord])
let step = 1
while (one.size && two.size) {
let temp = new Set()
if (two.size < one.size) [one, two] = [two, one]
for (const word of one) {
for (let i = 0; i  <  word.length; i++) {
for (let j = 0; j  <  26; j++) {
const candidate =
word.slice(0, i) + String.fromCharCode(97 + j) + word.slice(i + 1)
if (two.has(candidate)) return step + 1
if (!list.has(candidate)) continue
list.delete(candidate)
}
}
}
;[one, temp] = [temp, one]
step++
}
return 0
}
``````
Copy The Code &

Input

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

#4 Code Example with Python Programming

```Code - Python Programming```

``````
class Solution:
words, layer = set(wordList), {beginWord: [[beginWord]]}
while layer:
newlayer = collections.defaultdict(list)
for w in layer:
if w == endWord:
return len(layer[w][0])
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 0
``````
Copy The Code &

Input

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

#5 Code Example with C# Programming

```Code - C# Programming```

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

namespace LeetCode
{
{
public int LadderLength(string beginWord, string endWord, IList < string> wordList)
{
var map = new HashSet(wordList);
if (!map.Contains(endWord))
return 0;
var wordLength = beginWord.Length;

var used1 = new Dictionary < string, int>();
var used2 = new Dictionary();
used1[beginWord] = 1;
used2[endWord] = 1;

var queue1 = new Queue < string>();
var queue2 = new Queue();
queue1.Enqueue(beginWord);
queue2.Enqueue(endWord);

while (queue1.Count != 0 && queue2.Count != 0)
{
var str1 = queue1.Dequeue();
var str2 = queue2.Dequeue();

StringBuilder sb1 = new StringBuilder(str1);
StringBuilder sb2 = new StringBuilder(str2);

for (char i = 'a'; i  < = 'z'; i++)
{
for (int j = 0; j  <  wordLength; j++)
{
var temp = sb1[j];
sb1[j] = i;
var nextWord = sb1.ToString();
if (map.Contains(nextWord) && !used1.ContainsKey(nextWord))
{
if (used2.ContainsKey(nextWord))
{
return used2[nextWord] + used1[str1];
}
else
{
used1[nextWord] = used1[str1] + 1;
}
queue1.Enqueue(nextWord);
}
sb1[j] = temp;
}
for (int j = 0; j  <  wordLength; j++)
{
var temp = sb2[j];
sb2[j] = i;
var previousWord = sb2.ToString();
if (map.Contains(previousWord) && !used2.ContainsKey(previousWord))
{
if (used1.ContainsKey(previousWord))
{
return used1[previousWord] + used2[str2];
}
else
{
used2[previousWord] = used2[str2] + 1;
}
queue2.Enqueue(previousWord);
}
sb2[j] = temp;
}
}
}

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

Input

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