tgoop.com/easy_php_task/1242
Create:
Last Update:
Last Update:
Задача: 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"
class Solution {
function findLadders($beginWord, $endWord, $wordList) {
$adjList = [];
$wordSet = array_flip($wordList);
$this->bfs($beginWord, $endWord, $wordSet, $adjList);
$this->currPath = [$endWord];
$this->shortestPaths = [];
$this->backtrack($endWord, $beginWord, $adjList);
return $this->shortestPaths;
}
function findNeighbors($word, &$wordSet) {
$neighbors = [];
$charList = str_split($word);
for ($i = 0; $i < strlen($word); $i++) {
$oldChar = $charList[$i];
foreach (range('a', 'z') as $c) {
if ($c != $oldChar) {
$charList[$i] = $c;
$newWord = implode('', $charList);
if (isset($wordSet[$newWord])) {
$neighbors[] = $newWord;
}
}
}
$charList[$i] = $oldChar;
}
return $neighbors;
}
function backtrack($source, $destination, &$adjList) {
if ($source == $destination) {
$this->shortestPaths[] = array_reverse($this->currPath);
} else if (isset($adjList[$source])) {
foreach ($adjList[$source] as $neighbor) {
array_push($this->currPath, $neighbor);
$this->backtrack($neighbor, $destination, $adjList);
array_pop($this->currPath);
}
}
}
function bfs($beginWord, $endWord, &$wordSet, &$adjList) {
$queue = [$beginWord];
unset($wordSet[$beginWord]);
while ($queue) {
$currentWord = array_shift($queue);
$neighbors = $this->findNeighbors($currentWord, $wordSet);
foreach ($neighbors as $neighbor) {
$adjList[$neighbor][] = $currentWord;
if (isset($wordSet[$neighbor])) {
unset($wordSet[$neighbor]);
$queue[] = $neighbor;
}
}
}
}
}Ставь 👍 и забирай 📚 Базу знаний