#12HardFrom Research to FAANG · 33% acceptance

Shortest Transformation

BFSGraphString

Given a start word, an end word, and a dictionary, return the length of the shortest sequence transforming start into end, changing one letter at a time, where every intermediate word is in the dictionary.

If you have ever thought about minimal mutation paths between sequences, the framing will feel familiar — it is BFS on a graph you never explicitly built.

Examples

Input: begin="hit", end="cog", words=["hot","dot","dog","lot","log","cog"]

Output: 5

Note: hit → hot → dot → dog → cog.

Constraints

·All words have the same length.
·Words consist of lowercase letters.

Hints

solution.pyPython 3

from collections import deque

def ladder_length(begin, end, words):
    wordset = set(words)
    if end not in wordset:
        return 0
    q = deque([(begin, 1)])
    while q:
        word, steps = q.popleft()
        if word == end:
            return steps
        for i in range(len(word)):
            for c in "abcdefghijklmnopqrstuvwxyz":
                nxt = word[:i] + c + word[i+1:]
                if nxt in wordset:
                    wordset.remove(nxt)
                    q.append((nxt, steps + 1))
    return 0

Test console

// hit Run to execute the sample tests

// Interactive editor preview. Live code execution arrives with your early-access cohort.