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;
}
}
Ставь 👍 и забирай 📚 Базу знаний
2 · 365 ·