Q87: Word Ladder. - DSA Patterns (Multi-Lang)

In Simple Words: Shortest Path on unweighted graph using BFS: At each word, generate all 1-character wildcard variants (e.g. *ot, h*t, ho*). Transition to unvisited words matching any pattern. Return steps when reaching endWord.

Time: $O(M^2 \cdot N)$ | Space: $O(M^2 \cdot N)$

Multi-Language SolutionsPython 3 • JavaScript • TypeScript • Java • C++

Switch tabs or choose All

from collections import deque, defaultdict

def ladderLength(beginWord: str, endWord: str, wordList: list[str]) -> int:
    if endWord not in wordList: return 0
    patterns = defaultdict(list)
    for w in wordList:
        for i in range(len(w)):
            patterns[w[:i] + "*" + w[i+1:]].append(w)
    q = deque([beginWord])
    visited = {beginWord}
    res = 1
    while q:
        for _ in range(len(q)):
            word = q.popleft()
            if word == endWord: return res
            for j in range(len(word)):
                pattern = word[:j] + "*" + word[j+1:]
                for nei in patterns[pattern]:
                    if nei not in visited:
                        visited.add(nei)
                        q.append(nei)
        res += 1
    return 0