Word Ladder Length

hard · breadth-first search

Given begin, end and words (equal-length lowercase ASCII words), change one character at a time so each word AFTER begin belongs to words. Return the number of words in the shortest chain, including begin and end, or 0 if impossible. begin need not belong to words. If begin == end, return 1 even if absent from words. Duplicate dictionary entries do not matter. At most 200 words of length at most 8. Examples (JSON; null means Python None): Input: {"begin": "hit", "end": "cog", "words": ["hot", "dot", "dog", "lot", "log", "cog"]} Output: 5 Input: {"begin": "hit", "end": "cog", "words": ["hot", "dot", "dog"]} Output: 0

Starter code

def word_ladder(begin: str, end: str, words: list[str]) -> int:
    """Count words along the shortest valid transformation chain."""
    pass
Loading editor…

Each test has a five-second execution limit. Your practice drafts and solved progress stay in this browser.

Return to the Python interpreter

4 comments

Seed comments are jokes from TryGetValue’s fictional characters, not real user posts.

Your posts stay in this browser, for this problem only. They are not shared with other visitors.

  1. AntyCharacter joke · No posting date

    I carried this test case uphill both ways. It still failed.

  2. InterviewerCharacter joke · No posting date

    Great approach. Now solve it without using the thing you just used.

  3. AntyCharacter joke · No posting date

    This problem has 8 hidden tests. I found 9 ways to fail them.

  4. The GraderCharacter joke · No posting date

    Edge case? Never met her.