🔒Открыть пост
и посмотреть медиа
и посмотреть медиа
Задача: 126.Word Ladder II
Сложность: hard
Последовательность преобразований от слова beginWord до слова endWord с использованием словаря wordList — это последовательность слов beginWord -> s1 -> s2 -> ... -> sk, для которой выполняются следующие условия:
Каждая пара соседних слов отличается ровно одной буквой.
Каждое si для 1 "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 adjList = new HashMap();
List currPath = new ArrayList();
List
• > shortestPaths = new ArrayList();
private List findNeighbors(String word, Set wordList) {
List neighbors = new ArrayList();
char[] charList = word.toCharArray();
for (int i = 0; i < word.length(); i++) {
char oldChar = charList[i];
for (char c = 'a'; c 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
• > findLadders(String beginWord, String endWord, List wordList) {
bfs(beginWord, new HashSet(wordList));
currPath.add(endWord);
backtrack(endWord, beginWord);
return shortestPaths;
}
}
Ставь 👍 и забирай 📚 Базу знаний
