Word Ladder II solution and explanation

from collections import defaultdict, deque

def findLadders(beginWord, endWord, wordList):
    def construct_paths(source, destination, tree):
        if source == destination:
            return [[source]]
        return [[source] + path for succ in tree[source] for path in construct_paths(succ, destination, tree)]

    if endWord not in wordList or not endWord or not beginWord or not wordList:
        return []
    tree, words, n = defaultdict(set), set(wordList), len(beginWord)
    found, q, nq = False, {beginWord}, set()
    while q and not found:
        words -= q
        for x in q:
            for y in ([x[:i] + chr(c) + x[i+1:] for c in range(ord('a'), ord('z')+1)] for i in range(n)):
                for z in y:
                    if z in words:
                        if z == endWord:
                            found = True
                        else:
                            nq.add(z)
                        tree[x].add(z)
        q, nq = nq, set()
    return construct_paths(beginWord, endWord, tree)

import java.util.*;

public class WordLadderII {
    public List<List<String>> findLadders(String beginWord, String endWord, List<String> wordList) {
        List<List<String>> results = new ArrayList<>();
        Set<String> wordSet = new HashSet<>(wordList);
        if (!wordSet.contains(endWord)) return results;

        Map<String, List<String>> tree = new HashMap<>();
        if (!bfsGraph(tree, beginWord, endWord, wordSet)) return results;

        List<String> temp = new ArrayList<>();
        temp.add(beginWord);
        dfsFindPaths(results, temp, beginWord, endWord, tree);
        return results;
    }

    private boolean bfsGraph(Map<String, List<String>> tree, String beginWord, String endWord, Set<String> wordSet) {
        Queue<String> queue = new LinkedList<>();
        Set<String> visited = new HashSet<>();
        queue.add(beginWord);
        boolean found = false;
        Set<String> tempSet;

        while (!queue.isEmpty() && !found) {
            tempSet = new HashSet<>();
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                String word = queue.poll();
                for (String transformed : getTransforms(word)) {
                    if (transformed.equals(endWord)) found = true;

                    if (wordSet.contains(transformed) && visited.add(transformed)) {
                        tempSet.add(transformed);
                        queue.add(transformed);
                        tree.computeIfAbsent(word, k -> new ArrayList<>()).add(transformed);
                    }
                }
            }
            wordSet.removeAll(tempSet);
        }
        return found;
    }

    private List<String> getTransforms(String word) {
        List<String> transformations = new ArrayList<>();
        char[] charArray = word.toCharArray();
        for (int i = 0; i < charArray.length; i++) {
            char old = charArray[i];
            for (char c = 'a'; c <= 'z'; c++) {
                charArray[i] = c;
                transformations.add(new String(charArray));
            }
            charArray[i] = old;
        }
        return transformations;
    }

    private void dfsFindPaths(List<List<String>> results, List<String> path, String word, String endWord, Map<String, List<String>> tree) {
        if (word.equals(endWord)) {
            results.add(new ArrayList<>(path));
            return;
        }
        if (!tree.containsKey(word)) return;
        for (String next : tree.get(word)) {
            path.add(next);
            dfsFindPaths(results, path, next, endWord, tree);
            path.remove(path.size() - 1);
        }
    }
}

function findLadders(beginWord, endWord, wordList) {
    const tree = new Map();
    const wordSet = new Set(wordList);
    if (!wordSet.has(endWord)) return [];
    let found = false;
    let q = new Set([beginWord]);
    while (q.size && !found) {
        wordSet.forEach(
            word => q.has(word) ? wordSet.delete(word) : null
        );
        const nextSet = new Set();
        for (let word of q) {
            for (let i = 0; i < word.length; i++) {
                for (let j = 97; j <= 122; j++) {
                    const newWord = word.slice(0, i) + String.fromCharCode(j) + word.slice(i + 1);
                    if (wordSet.has(newWord) || newWord == endWord) {
                        if (!tree.has(word)) tree.set(word, []);
                        tree.get(word).push(newWord);
                        if (newWord == endWord) found = true;
                        nextSet.add(newWord);
                    }
                }
            }
        }
        q = nextSet;
    }

    const res = [];
    function dfs(word, path) {
        if (word === endWord) {
            res.push([...path, word]);
            return;
        }
        if (tree.has(word)) {
            for (let next of tree.get(word)) {
                dfs(next, [...path, word]);
            }
        }
    }
    dfs(beginWord, []);
    return res;
}

#include <iostream>
#include <vector>
#include <string>
#include <queue>
#include <unordered_set>
using namespace std;

vector<vector<string>> findLadders(string beginWord, string endWord, vector<string>& wordList) {
    unordered_set<string> wordSet(wordList.begin(), wordList.end());
    vector<vector<string>> result;
    if (wordSet.find(endWord) == wordSet.end()) return result;

    queue<vector<string>> paths;
    paths.push({beginWord});
    vector<string> visited;

    while (!paths.empty()) {
        int levelSize = paths.size();
        unordered_set<string> currentLevelVisited;

        while (levelSize--) {
            vector<string> path = paths.front(); paths.pop();
            string lastWord = path.back();

            vector<string> newVisited;
            for (int i = 0; i < lastWord.length(); ++i) {
                char original = lastWord[i];
                for (char c = 'a'; c <= 'z'; ++c) {
                    lastWord[i] = c;
                    if (lastWord == endWord) {
                        path.push_back(endWord);
                        result.push_back(path);
                    }
                    if (wordSet.find(lastWord) != wordSet.end()) {
                        vector<string> newPath = path;
                        newPath.push_back(lastWord);
                        paths.push(newPath);
                        currentLevelVisited.insert(lastWord);
                    }
                }
                lastWord[i] = original;
            }
        }
        for (const string& word : currentLevelVisited) {
            wordSet.erase(word);
        }
        if (!result.empty()) break;
    }
    return result;
}

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <string.h>

typedef struct Node {
    char *word;
    struct Node *prev;
    struct Node *next;
} Node;

typedef struct Queue {
    Node *front;
    Node *rear;
} Queue;

Queue *initQueue() {
    Queue *q = (Queue *)malloc(sizeof(Queue));
    q->front = q->rear = NULL;
    return q;
}

void enqueue(Queue *q, char *word) {
    Node *newNode = (Node *)malloc(sizeof(Node));
    newNode->word = strdup(word);
    newNode->next = NULL;
    if (q->rear) {
        q->rear->next = newNode;
    } else {
        q->front = newNode;
    }
    q->rear = newNode;
}

char *dequeue(Queue *q) {
    if (!q->front) return NULL;
    Node *node = q->front;
    char *word = node->word;
    q->front = q->front->next;
    if (!q->front) {
        q->rear = NULL;
    }
    free(node);
    return word;
}

bool queueIsEmpty(Queue *q) {
    return q->front == NULL;
}

void freeQueue(Queue *q) {
    while (!queueIsEmpty(q)) {
        free(dequeue(q));
    }
    free(q);
}

bool isOneLetterDiff(char *word1, char *word2) {
    int diff = 0;
    for (int i = 0; word1[i]; i++) {
        if (word1[i] != word2[i]) diff++;
        if (diff > 1) return false;
    }
    return diff == 1;
}

char *getTransformedWord(char *word, int index, char c) {
    char *transformedWord = strdup(word);
    transformedWord[index] = c;
    return transformedWord;
}

char **findLadders(char *beginWord, char *endWord, char **wordList, int wordListSize, int *returnSize) {
    Queue *queue = initQueue();
    enqueue(queue, beginWord);

    char visited[wordListSize];
    for (int i = 0; i < wordListSize; i++) visited[i] = 0;
    *returnSize = 0;
    char **result = (char **)malloc(sizeof(char *) * wordListSize);
    while (!queueIsEmpty(queue)) {
        int levelSize = 0;
        Queue *nextLevel = initQueue();
        while (!queueIsEmpty(queue)) {
            char *word = dequeue(queue);
            for (int i = 0; i < wordListSize; i++) {
                if (!visited[i] && isOneLetterDiff(word, wordList[i])) {
                    if (strcmp(wordList[i], endWord) == 0) {
                        result[(*returnSize)++] = strdup(wordList[i]);
                    }
                    enqueue(nextLevel, wordList[i]);
                    visited[i] = 1;
                }
            }
            free(word);
        }
        freeQueue(queue);
        queue = nextLevel;
    }
    return result;
}

using System;
using System.Collections.Generic;

public class Solution {
    public IList<IList<string>> FindLadders(string beginWord, string endWord, IList<string> wordList) {
        var wordSet = new HashSet<string>(wordList);
        var results = new List<IList<string>>();
        if (!wordSet.Contains(endWord)) return results;

        var queue = new Queue<IList<string>>();
        queue.Enqueue(new List<string>(){beginWord});
        var levelVisited = new HashSet<string>();

        while (queue.Count > 0) {
            int levelSize = queue.Count;
            var currentLevelVisited = new HashSet<string>();

            while (levelSize-- > 0) {
                var currentPath = queue.Dequeue();
                var lastWord = currentPath[currentPath.Count - 1];

                if (lastWord.Equals(endWord)) {
                    results.Add(currentPath);
                }

                for (int i = 0; i < lastWord.Length; i++) {
                    char[] currentWordArr = lastWord.ToCharArray();
                    for (char c = 'a'; c <= 'z'; c++) {
                        currentWordArr[i] = c;
                        var newWord = new string(currentWordArr);

                        if (wordSet.Contains(newWord) && !levelVisited.Contains(newWord)) {
                            var newPath = new List<string>(currentPath);
                            newPath.Add(newWord);
                            queue.Enqueue(newPath);
                            currentLevelVisited.Add(newWord);
                        }
                    }
                }
            }
            foreach (var word in currentLevelVisited) {
                wordSet.Remove(word);
                levelVisited.Add(word);
            }
            if (results.Count > 0) break;
        }
        return results;
    }
}

func findLadders(beginWord string, endWord string, wordList []string) [][]string {
	var ans [][]string
	words := make(map[string]bool)
	for _, word := range wordList {
		words[word] = true
	}
	if !words[endWord] {
		return ans
	}
	words[beginWord] = false
	dist := map[string]int{beginWord: 0}
	prev := map[string]map[string]bool{}
	q := []string{beginWord}
	found := false
	step := 0
	for len(q) > 0 && !found {
		step++
		for i := len(q); i > 0; i-- {
			p := q[0]
			q = q[1:]
			chars := []byte(p)
			for j := 0; j < len(chars); j++ {
				ch := chars[j]
				for k := 'a'; k <= 'z'; k++ {
					chars[j] = byte(k)
					t := string(chars)
					if v, ok := dist[t]; ok {
						if v == step {
							prev[t][p] = true
						}
					}
					if !words[t] {
						continue
					}
					if len(prev[t]) == 0 {
						prev[t] = make(map[string]bool)
					}
					prev[t][p] = true
					words[t] = false
					q = append(q, t)
					dist[t] = step
					if endWord == t {
						found = true
					}
				}
				chars[j] = ch
			}
		}
	}
	var dfs func(path []string, begin, cur string)
	dfs = func(path []string, begin, cur string) {
		if cur == beginWord {
			cp := make([]string, len(path))
			copy(cp, path)
			ans = append(ans, cp)
			return
		}
		for k := range prev[cur] {
			path = append([]string{k}, path...)
			dfs(path, beginWord, k)
			path = path[1:]
		}
	}
	if found {
		path := []string{endWord}
		dfs(path, beginWord, endWord)
	}
	return ans
}