Leetcode: 126. Word Ladder II

Pattern: Find all shortest path between two vertices in a graph. Find the min distance between destination and all other vertices using a Breadth-first search, then generate all shortest path using the acyclic path created by the first search using Depth-first search. Time and space complexity are \(O(n)\).

from typing import List


class Solution:
    def findLadders(
        self, beginWord: str, endWord: str, wordList: List[str]
    ) -> List[List[str]]:
        def is_adj(u, v):
            return sum(1 for a, b in zip(u, v) if a != b) == 1

        A = {w: [] for w in wordList + [beginWord, endWord]}
        for u in wordList + [endWord]:
            for v in wordList + [beginWord]:
                if u != v and is_adj(u, v):
                    A[u].append(v)

        dist = {w: None for w in A}
        dist[endWord] = 0
        queue = [endWord]
        for u in queue:
            for v in A[u]:
                if dist[v] is None:
                    dist[v] = dist[u] + 1
                    queue.append(v)

        ans = []
        for u in wordList:
            if u != beginWord and u not in A[beginWord] and is_adj(u, beginWord):
                A[beginWord].append(u)

        @cache
        def dfs(u):
            if dist[u] == 0:
                return [[u]]
            ans = []
            for v in A[u]:
                if dist[v] == dist[u] - 1:
                    ans.extend([u] + p for p in dfs(v))
            return ans

        return dfs(beginWord)