Word Ladder

def ladderLength(beginWord, endWord, wordList):
    def one_letter_apart(a, b):
        differences = 0
        for x, y in zip(a, b):
            if x != y:
                differences += 1
                if differences > 1:
                    return False
        return differences == 1

    best = 0  # words in the shortest sequence found so far, 0 while there is none
    used = [word == beginWord for word in wordList]  # words on the current path

    def search(word, length):
        nonlocal best
        if word == endWord:
            if best == 0 or length < best:
                best = length
            return
        if best != 0 and length + 1 >= best:
            return  # any longer path cannot beat the best one
        for i, candidate in enumerate(wordList):
            if not used[i] and one_letter_apart(word, candidate):
                used[i] = True
                search(candidate, length + 1)
                used[i] = False  # free the word for other paths

    search(beginWord, 1)
    return best

from collections import deque


def ladderLength(beginWord, endWord, wordList):
    def one_letter_apart(a, b):
        differences = 0
        for x, y in zip(a, b):
            if x != y:
                differences += 1
                if differences > 1:
                    return False
        return differences == 1

    if endWord not in wordList:
        return 0
    visited = [word == beginWord for word in wordList]
    queue = deque([(beginWord, 1)])  # (word, words in the sequence up to it)
    while queue:
        word, length = queue.popleft()
        # Compare against every word to find the neighbours.
        for i, candidate in enumerate(wordList):
            if not visited[i] and one_letter_apart(word, candidate):
                if candidate == endWord:
                    return length + 1
                visited[i] = True
                queue.append((candidate, length + 1))
    return 0

from collections import defaultdict, deque


def ladderLength(beginWord, endWord, wordList):
    if endWord not in wordList:
        return 0
    size = len(beginWord)
    # "h*t" -> every word that matches it: hot, hat, hit... are one letter apart.
    buckets = defaultdict(list)
    for word in set(wordList) | {beginWord}:
        for i in range(size):
            buckets[word[:i] + "*" + word[i + 1:]].append(word)
    visited = {beginWord}
    queue = deque([beginWord])
    length = 1  # words in the sequence up to the current level
    while queue:
        for _ in range(len(queue)):  # one level: every word at this distance
            word = queue.popleft()
            if word == endWord:
                return length
            for i in range(size):
                pattern = word[:i] + "*" + word[i + 1:]
                for neighbour in buckets[pattern]:
                    if neighbour not in visited:
                        visited.add(neighbour)
                        queue.append(neighbour)
                buckets[pattern] = []  # all of them are visited now: never scan it again
        length += 1
    return 0