Java | LeetCode

Задача: 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.

😎

Решение:

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

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

Please open Telegram to view this post