06 Jun 2024•PHP•Hard

Word Ladder II

find all shortest transformation sequences from beginWord to endWord using bfs with path tracking.

first bfs to find shortest distance to endWord. then dfs backwards from endWord, only following edges that lead to words at distance d-1, building all paths.

build graph during first bfs: map each word to its neighbors. use distance map to track shortest distance to each word. second pass collects all valid paths.

two-phase approach

phase 1: bfs to find shortest distance
phase 2: dfs to collect all shortest paths
only traverse edges that maintain distance constraint

complexity

O(m * n * 26) for bfs, O(2^d) worst case for dfs where d is depth. space O(n) for graph and paths.

Solution files

PHP•word-ladder-2/solution.php

class Solution {

function findLadders($beginWord, $endWord, $wordList) {
    $wordSet = array_flip($wordList);
    if (!isset($wordSet[$endWord])) {
        return [];
    }

    $queue = new SplQueue();
    $queue->enqueue([$beginWord]);
    $results = [];
    $found = false;
    $visited = [];

    while (!$queue->isEmpty() && !$found) {
        $levelVisited = [];

        for ($i = $queue->count(); $i > class="syntax-number">0; $i--) {
            $path = $queue->dequeue();
            $word = end($path);

            foreach ($this->getNextWords($word, $wordSet) as $nextWord) {
                if (isset($visited[$nextWord])) {
                    continue;
                }

                $newPath = $path;
                $newPath[] = $nextWord;

                if ($nextWord === $endWord) {
                    $results[] = $newPath;
                    $found = true;
                } else {
                    $queue->enqueue($newPath);
                    $levelVisited[$nextWord] = true;
                }
            }
        }

        foreach ($levelVisited as $word => $val) {
            $visited[$word] = true;
        }
    }

    return $results;
}

private function getNextWords($word, $wordSet) {
    $nextWords = [];
    $wordArray = str_split($word);
    for ($i = class="syntax-number">0; $i < count($wordArray); $i++) {
        $originalChar = $wordArray[$i];
        for ($c = ord(class="syntax-string">'a'); $c <= ord(class="syntax-string">'z'); $c++) {
            $wordArray[$i] = chr($c);
            $newWord = implode(class="syntax-string">'', $wordArray);
            if ($newWord !== $word && isset($wordSet[$newWord])) {
                $nextWords[] = $newWord;
            }
        }
        $wordArray[$i] = $originalChar;
    }
    return $nextWords;
}
}