Algorithm
Problem Name: 127. Word Ladder
problem Link: https://leetcode.com/problems/word-ladder/
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
sifor1 <= i <= kis inwordList. Note thatbeginWorddoes not need to be inwordList. 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 <= 10endWord.length == beginWord.length1 <= wordList.length <= 5000wordList[i].length == beginWord.lengthbeginWord,endWord, andwordList[i]consist of lowercase English letters.beginWord != endWord- All the words in
wordListare 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;
}
Input
beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log","cog"]
Output
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;
}
};
Input
beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log","cog"]
Output
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
temp.add(candidate)
list.delete(candidate)
}
}
}
;[one, temp] = [temp, one]
step++
}
return 0
}
Input
beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log"]
#4 Code Example with Python Programming
Code -
Python Programming
class Solution:
def ladderLength(self, beginWord, endWord, wordList):
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
Input
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 class _0127_WordLadder
{
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;
}
}
}
Input
beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log"]