Leetcode: 127. Word Ladder

Problem Statement

Understand the problem

Pattern: Find shortest path between two vertices in a graph where vertices are words and two words are adjacent if they differ only by one letter.

Devise a plan

This is a classic example of Breadth-first search. The only thing to look out is how to efficiently generate the edges of the graph. By inspecting the constraints, you will find that we can generate the next word and then check if it is an vertex in the graph. Time complexity is \(O(n^2)\) and space is \(O(n)\).

Carry out the plan

from typing import List
import string


class Solution:
    def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:
        D = set(wordList)
        C = {c for w in wordList + [beginWord] for c in w}
        queue = [(0, beginWord)]
        seen = set()
        for steps, u in queue:
            if u == endWord:
                return steps + 1
            for i in range(len(u)):
                for c in C:
                    if c == u[i]:
                        continue
                    v = u[:i] + c + u[i + 1 :]
                    if v not in seen and v in D:
                        seen.add(v)
                        queue.append((steps + 1, v))
        return 0


assert (
    Solution().ladderLength("hit", "cog", ["hot", "dot", "dog", "lot", "log", "cog"])
    == 5
)
assert Solution().ladderLength("hit", "cog", ["hot", "dot", "dog", "lot", "log"]) == 0