Algorithm
Problem Name: 126. Word Ladder II
problem Link: https://leetcode.com/problems/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
sifor1 <= i <= kis inwordList. Note thatbeginWorddoes not need to be inwordList. 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 <= 5endWord.length == beginWord.length1 <= wordList.length <= 500wordList[i].length == beginWord.lengthbeginWord,endWord, andwordList[i]consist of lowercase English letters.beginWord != endWord- All the words in
wordListare 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;
add2res(res, buff, l);
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
}
add2prev(b, a->idx); // add a as a preceeding node of b
}
}
}
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;
}
Input
beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log","cog"]
Output
[["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)) {
set.add(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
}
Input
beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log","cog"]
Output
[["hit","hot","dot","dog","cog"],["hit","hot","lot","log","cog"]]
#3 Code Example with Python Programming
Code -
Python Programming
class Solution:
def findLadders(self, beginWord, endWord, wordList):
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
Input
beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log"]
Output
[]
#4 Code Example with C# Programming
Code -
C# Programming
using System.Collections.Generic;
namespace LeetCode
{
public class _0126_WordLadderII
{
public IList < IList wordList)
{
var map = new HashSet(wordList);
if (!map.Contains(endWord))
return new List() { beginWord });
return answer;
}
private void FindLadders(string beginWord, string endWord, IDictionary < string, HashSet solution)
{
if (beginWord == endWord)
{
answer.Add(new List(solution));
return;
}
if (!graph.ContainsKey(beginWord)) return;
foreach (var word in graph[beginWord])
{
solution.Add(word);
FindLadders(word, endWord, graph, answer, solution);
solution.RemoveAt(solution.Count - 1);
}
}
private bool BuildGraph(string beginWord, string endWord, HashSet < string> wordList, IDictionary();
var used2 = new HashSet();
used1.Add(beginWord);
used2.Add(endWord);
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>());
graph[parent].Add(child);
}
if (wordList.Contains(nextWord) && !done)
{
current_used.Add(nextWord);
if (!graph.ContainsKey(parent)) graph.Add(parent, new HashSet < string>());
graph[parent].Add(child);
}
}
charArray[j] = temp;
}
}
used1 = current_used;
}
return done;
}
}
}
Input
beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log"]
Output
[]