126. Word Ladder II

public class Solution {
    Dictionary<string, List<string>> adjList = new Dictionary<string, List<string>>();
    List<string> currPath = new List<string>();
    List<IList<string>> shortestPaths = new List<IList<string>>();
    private List<string> FindNeighbors(string word, HashSet<string> wordList) {
        List<string> neighbors = new List<string>();
        char[] charList = word.ToCharArray();
        for (int i = 0; i < word.Length; i++) {
            char oldChar = charList[i];
            for (char c = 'a'; c <= 'z'; c++) {
                if (c != oldChar) {
                    charList[i] = c;
                    string newWord = new string(charList);
                    if (wordList.Contains(newWord)) neighbors.Add(newWord);
                }
            }
            charList[i] = oldChar;
        }
        return neighbors;
    }
    private void Backtrack(string source, string destination) {
        if (source == destination) {
            var tempPath = new List<string>(currPath);
            tempPath.Reverse();
            shortestPaths.Add(tempPath);
            return;
        }
        if (adjList.ContainsKey(source)) {
            foreach (var neighbor in adjList[source]) {
                currPath.Add(neighbor);
                Backtrack(neighbor, destination);
                currPath.RemoveAt(currPath.Count - 1);
            }
        }
    }
    private void Bfs(string beginWord, HashSet<string> wordList) {
        Queue<string> q = new Queue<string>(new[] { beginWord });
        wordList.Remove(beginWord);
        while (q.Count > 0) {
            for (int i = q.Count; i > 0; i--) {
                var currWord = q.Dequeue();
                foreach (var neighbor in FindNeighbors(currWord, wordList)) {
                    if (!adjList.TryGetValue(neighbor, out var list)) {
                        list = adjList[neighbor] = new List<string>();
                        q.Enqueue(neighbor);
                    }
                    list.Add(currWord);
                }
            }
        }
    }
    public IList<IList<string>> FindLadders(string beginWord, string endWord, IList<string> wordList) {
        Bfs(beginWord, new HashSet<string>(wordList));
        currPath.Add(endWord);
        Backtrack(endWord, beginWord);
        return shortestPaths;
    }
}

#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
    unordered_map<string, List<string>> adjList = new unordered_map<string, List<string>>();
    List<string> currPath = new List<string>();
    List<vector<string>> shortestPaths = new List<vector<string>>();
    private List<string> FindNeighbors(string word, HashSet<string> wordList) {
        List<string> neighbors = new List<string>();
        char[] charList = word.ToCharArray();
        for (int i = 0; i < word.size(); i++) {
            char oldChar = charList[i];
            for (char c = 'a'; c <= 'z'; c++) {
                if (c != oldChar) {
                    charList[i] = c;
                    string newWord = new string(charList);
                    if (wordList.Contains(newWord)) neighbors.push_back(newWord);
                }
            }
            charList[i] = oldChar;
        }
        return neighbors;
    }
    private void Backtrack(string source, string destination) {
        if (source == destination) {
            var tempPath = new List<string>(currPath);
            tempPath.Reverse();
            shortestPaths.push_back(tempPath);
            return;
        }
        if (adjList.count(source)) {
            foreach (var neighbor in adjList[source]) {
                currPath.push_back(neighbor);
                Backtrack(neighbor, destination);
                currPath.RemoveAt(currPath.size() - 1);
            }
        }
    }
    private void Bfs(string beginWord, HashSet<string> wordList) {
        queue<string> q = new queue<string>(new[] { beginWord });
        wordList.Remove(beginWord);
        while (q.size() > 0) {
            for (int i = q.size(); i > 0; i--) {
                var currWord = q.Dequeue();
                foreach (var neighbor in FindNeighbors(currWord, wordList)) {
                    if (!adjList.TryGetValue(neighbor, out var list)) {
                        list = adjList[neighbor] = new List<string>();
                        q.Enqueue(neighbor);
                    }
                    list.push_back(currWord);
                }
            }
        }
    }
    public IList<vector<string>> FindLadders(string beginWord, string endWord, vector<string> wordList) {
        Bfs(beginWord, new HashSet<string>(wordList));
        currPath.push_back(endWord);
        Backtrack(endWord, beginWord);
        return shortestPaths;
    }
}

class Solution {
    Map<String, List<String>> adjList = new HashMap<>();
    List<String> currPath = new ArrayList<>();
    List<List<String>> shortestPaths = new ArrayList<>();

    private List<String> findNeighbors(String word, Set<String> wordList) {
        List<String> neighbors = new ArrayList<>();
        char[] charList = word.toCharArray();
        for (int i = 0; i < word.length(); i++) {
            char oldChar = charList[i];
            for (char c = 'a'; c <= 'z'; c++) {
                if (c == oldChar) continue;
                charList[i] = c;
                String newWord = String.valueOf(charList);
                if (wordList.contains(newWord)) neighbors.add(newWord);
            }
            charList[i] = oldChar;
        }
        return neighbors;
    }

    private void backtrack(String source, String destination) {
        if (source.equals(destination)) {
            Collections.reverse(currPath);
            shortestPaths.add(new ArrayList<>(currPath));
            Collections.reverse(currPath);
        }

        if (!adjList.containsKey(source)) return;

        for (String neighbor : adjList.get(source)) {
            currPath.add(neighbor);
            backtrack(neighbor, destination);
            currPath.remove(currPath.size() - 1);
        }
    }

    private void bfs(String beginWord, Set<String> wordList) {
        Queue<String> queue = new LinkedList<>();
        queue.add(beginWord);
        wordList.remove(beginWord);

        while (!queue.isEmpty()) {
            int size = queue.size();
            while (size-- > 0) {
                String currentWord = queue.poll();
                for (String neighbor : findNeighbors(currentWord, wordList)) {
                    adjList.computeIfAbsent(neighbor, k -> new ArrayList<>()).add(currentWord);
                    if (wordList.remove(neighbor)) queue.add(neighbor);
                }
            }
        }
    }

    public List<List<String>> findLadders(String beginWord, String endWord, List<String> wordList) {
        bfs(beginWord, new HashSet<>(wordList));
        currPath.add(endWord);
        backtrack(endWord, beginWord);
        return shortestPaths;
    }
}

var findLadders = function(beginWord, endWord, wordList) {
    let adjList = {};
    let currPath = [endWord];
    let shortestPaths = [];
    let wordSet = new Set(wordList);

    function findNeighbors(word) {
        let neighbors = [];
        let charList = Array.from(word);
        for (let i = 0; i < charList.length; i++) {
            let oldChar = charList[i];
            for (let c = 'a'.charCodeAt(0); c <= 'z'.charCodeAt(0); c++) {
                if (c !== oldChar.charCodeAt(0)) {
                    charList[i] = String.fromCharCode(c);
                    let newWord = charList.join("");
                    if (wordSet.has(newWord)) neighbors.push(newWord);
                }
            }
            charList[i] = oldChar;
        }
        return neighbors;
    }

    function backtrack(source) {
        if (source === endWord) {
            shortestPaths.push([...currPath].reverse());
            return;
        }
        adjList[source]?.forEach(neighbor => {
            currPath.push(neighbor);
            backtrack(neighbor);
            currPath.pop();
        });
    }

    function bfs() {
        let queue = [beginWord];
        wordSet.delete(beginWord);
        while (queue.length) {
            let current = queue.shift();
            let neighbors = findNeighbors(current);
            neighbors.forEach(neighbor => {
                if (!adjList[neighbor]) adjList[neighbor] = [];
                adjList[neighbor].push(current);
                if (!wordSet.has(neighbor)) {
                    queue.push(neighbor);
                    wordSet.delete(neighbor);
                }
            });
        }
    }

    bfs();
    backtrack(beginWord);
    return shortestPaths;
};

class Solution:
    def __init__(self):
        self.adjList = {}
        self.currPath = []
        self.shortestPaths = []

    def findNeighbors(self, word, wordSet):
        neighbors = []
        charList = list(word)
        for i in range(len(charList)):
            oldChar = charList[i]
            for c in "abcdefghijklmnopqrstuvwxyz":
                if c != oldChar:
                    charList[i] = c
                    newWord = "".join(charList)
                    if newWord in wordSet:
                        neighbors.append(newWord)
            charList[i] = oldChar
        return neighbors

    def backtrack(self, source, destination):
        if source == destination:
            self.shortestPaths.append(self.currPath[::-1])

        for neighbor in self.adjList.get(source, []):
            self.currPath.append(neighbor)
            self.backtrack(neighbor, destination)
            self.currPath.pop()

    def bfs(self, beginWord, endWord, wordSet):
        q = deque([beginWord])
        wordSet.discard(beginWord)
        isEnqueued = {beginWord: True}
        
        while q:
            visited = []
            for _ in range(len(q)):
                currWord = q.popleft()
                neighbors = self.findNeighbors(currWord, wordSet)
                for neighbor in neighbors:
                    if neighbor not in isEnqueued:
                        q.append(neighbor)
                        isEnqueued[neighbor] = True
                        self.adjList[neighbor] = []
                    self.adjList[neighbor].append(currWord)
                    visited.append(neighbor)
            
            for word in visited:
                wordSet.discard(word)

    def findLadders(self, beginWord, endWord, wordList):
        wordSet = set(wordList)
        self.bfs(beginWord, endWord, wordSet)
        self.currPath = [endWord]
        self.backtrack(endWord, beginWord)
        return self.shortestPaths

func findLadders(beginWord, endWord string, wordList []string) [][]string {
    adjList := make(map[string][]string)
    wordSet := make(map[string]bool)
    for _, word := range wordList {
        wordSet[word] = true
    }

    bfs(beginWord, wordSet, adjList)
    var currPath []string
    var shortestPaths [][]string
    currPath = append(currPath, endWord)
    backtrack(endWord, beginWord, &currPath, &shortestPaths, adjList)
    return shortestPaths
}

func findNeighbors(word string, wordSet map[string]bool) []string {
    var neighbors []string
    charList := []rune(word)
    for i := range charList {
        oldChar := charList[i]
        for c := 'a'; c <= 'z'; c++ {
            if c != oldChar {
                charList[i] = c
                newWord := string(charList)
                if wordSet[newWord] {
                    neighbors = append(neighbors, newWord)
                }
            }
        }
        charList[i] = oldChar
    }
    return neighbors
}

func backtrack(source, destination string, currPath *[]string, shortestPaths *[][]string, adjList map[string][]string) {
    if source == destination {
        pathCopy := make([]string, len(*currPath))
        copy(pathCopy, *currPath)
        reverse(pathCopy)
        *shortestPaths = append(*shortestPaths, pathCopy)
        return
    }
    for _, neighbor := range adjList[source] {
        *currPath = append(*currPath, neighbor)
        backtrack(neighbor, destination, currPath, shortestPaths, adjList)
        *currPath = (*currPath)[:len(*currPath)-1]
    }
}

func bfs(beginWord string, wordSet map[string]bool, adjList map[string][]string) {
    queue := []string{beginWord}
    visited := make(map[string]bool)
    visited[beginWord] = true

    for len(queue) > 0 {
        current := queue[0]
        queue = queue[1:]
        neighbors := findNeighbors(current, wordSet)
        for _, neighbor := range neighbors {
            if !visited[neighbor] {
                visited[neighbor] = true
                queue = append(queue, neighbor)
                adjList[neighbor] = append(adjList[neighbor], current)
            }
        }
    }
}

func reverse(slice []string) {
    for i, j := 0, len(slice)-1; i < j; i, j = i+1, j-1 {
        slice[i], slice[j] = slice[j], slice[i]
    }
}

Algorithm

1️⃣

Сохранение слов из списка слов (wordList) в хэш-таблицу (unordered set) для эффективного удаления слов в процессе поиска в ширину (BFS).

2️⃣

Выполнение BFS, добавление связей в список смежности (adjList). После завершения уровня удалять посещенные слова из wordList.

3️⃣

Начать с beginWord и отслеживать текущий путь как currPath, просматривать все возможные пути, и когда путь ведет к endWord, сохранять путь в shortestPaths.

😎