Задача: 126.Word Ladder II
Сложность: hard

Последовательность преобразований от слова beginWord до слова endWord с использованием словаря wordList — это последовательность слов beginWord -> s1 -> s2 -> ... -> sk, для которой выполняются следующие условия:

Каждая пара соседних слов отличается ровно одной буквой.
Каждое si для 1 <= i <= k находится в wordList. Отметим, что beginWord не обязательно должно быть в wordList.
sk == endWord.
Для двух слов, beginWord и endWord, и словаря wordList, вернуть все самые короткие последовательности преобразований от beginWord до endWord или пустой список, если такая последовательность не существует. Каждая последовательность должна возвращаться в виде списка слов [beginWord, s1, s2, ..., sk].

Пример:

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"

👨‍💻 Алгоритм:

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

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

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

😎 Решение:

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;
    }
}

Ставь 👍 и забирай 📚 Базу знаний