Word Ladder

Problem#

Given beginWord, endWord, and a word list, return the length of the shortest sequence begin -> ... -> end where every adjacent pair differs by exactly one letter and every intermediate word is in the list. Return 0 if no such sequence exists.

Examples#

begin = "hit", end = "cog", words = ["hot","dot","dog","lot","log","cog"] → 5 (hit -> hot -> dot -> dog -> cog).
begin = "hit", end = "cog", words = ["hot","dot","dog","lot","log"] → 0.

Constraints#

1 <= L <= 10, 1 <= words.length <= 5000, all words same length.

Hints#

Hint 1

BFS treats unweighted graph distance as the answer; build adjacency lazily via wildcard patterns.

Hint 2

For each word, generating L wildcards like h*t gives constant-time neighbor lookup against a bucket map.

Approach#

Build a map from each wildcard pattern (e.g., h*t) to the words matching it. BFS from beginWord: for each popped word, for each of its L wildcards, enqueue every bucket-mate not yet visited.

Solution#

class Solution {
public:
    int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
        unordered_set<string> dict(wordList.begin(), wordList.end());
        if (!dict.count(endWord)) return 0;
        unordered_map<string, vector<string>> buckets;
        int L = beginWord.size();
        for (auto& w : dict) {
            for (int i = 0; i < L; ++i) {
                string key = w;
                key[i] = '*';
                buckets[key].push_back(w);
            }
        }
        queue<pair<string,int>> q;
        q.push({beginWord, 1});
        unordered_set<string> seen{beginWord};
        while (!q.empty()) {
            auto [w, d] = q.front(); q.pop();
            if (w == endWord) return d;
            for (int i = 0; i < L; ++i) {
                string key = w;
                key[i] = '*';
                auto it = buckets.find(key);
                if (it == buckets.end()) continue;
                for (auto& nx : it->second) {
                    if (seen.insert(nx).second) q.push({nx, d + 1});
                }
                it->second.clear();             // optional dedupe optimization
            }
        }
        return 0;
    }
};

func ladderLength(beginWord string, endWord string, wordList []string) int {
    dict := map[string]bool{}
    for _, w := range wordList {
        dict[w] = true
    }
    if !dict[endWord] {
        return 0
    }
    L := len(beginWord)
    buckets := map[string][]string{}
    for w := range dict {
        b := []byte(w)
        for i := 0; i < L; i++ {
            orig := b[i]
            b[i] = '*'
            key := string(b)
            buckets[key] = append(buckets[key], w)
            b[i] = orig
        }
    }
    type item struct {
        w string
        d int
    }
    q := []item{{beginWord, 1}}
    seen := map[string]bool{beginWord: true}
    for len(q) > 0 {
        cur := q[0]
        q = q[1:]
        if cur.w == endWord {
            return cur.d
        }
        b := []byte(cur.w)
        for i := 0; i < L; i++ {
            orig := b[i]
            b[i] = '*'
            key := string(b)
            b[i] = orig
            if nbrs, ok := buckets[key]; ok {
                for _, nx := range nbrs {
                    if !seen[nx] {
                        seen[nx] = true
                        q = append(q, item{nx, cur.d + 1})
                    }
                }
                buckets[key] = nil // optional dedupe optimization
            }
        }
    }
    return 0
}

from collections import defaultdict, deque
from typing import List

class Solution:
    def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:
        dict_set = set(wordList)
        if endWord not in dict_set:
            return 0
        L = len(beginWord)
        buckets: dict[str, list[str]] = defaultdict(list)
        for w in dict_set:
            for i in range(L):
                key = w[:i] + '*' + w[i + 1:]
                buckets[key].append(w)
        q: deque[tuple[str, int]] = deque([(beginWord, 1)])
        seen = {beginWord}
        while q:
            w, d = q.popleft()
            if w == endWord:
                return d
            for i in range(L):
                key = w[:i] + '*' + w[i + 1:]
                if key in buckets:
                    for nx in buckets[key]:
                        if nx not in seen:
                            seen.add(nx)
                            q.append((nx, d + 1))
                    buckets[key] = []  # optional dedupe optimization
        return 0

function ladderLength(beginWord, endWord, wordList) {
    const dict = new Set(wordList);
    if (!dict.has(endWord)) return 0;
    const L = beginWord.length;
    const buckets = new Map();
    for (const w of dict) {
        for (let i = 0; i < L; i++) {
            const key = w.slice(0, i) + '*' + w.slice(i + 1);
            if (!buckets.has(key)) buckets.set(key, []);
            buckets.get(key).push(w);
        }
    }
    let q = [[beginWord, 1]];
    const seen = new Set([beginWord]);
    while (q.length > 0) {
        const next = [];
        for (const [w, d] of q) {
            if (w === endWord) return d;
            for (let i = 0; i < L; i++) {
                const key = w.slice(0, i) + '*' + w.slice(i + 1);
                const nbrs = buckets.get(key);
                if (!nbrs) continue;
                for (const nx of nbrs) {
                    if (!seen.has(nx)) {
                        seen.add(nx);
                        next.push([nx, d + 1]);
                    }
                }
                buckets.set(key, []); // optional dedupe optimization
            }
        }
        q = next;
    }
    return 0;
}

class Solution {
    public int ladderLength(String beginWord, String endWord, List<String> wordList) {
        Set<String> dict = new HashSet<>(wordList);
        if (!dict.contains(endWord)) return 0;
        int L = beginWord.length();
        Map<String, List<String>> buckets = new HashMap<>();
        for (String w : dict) {
            char[] arr = w.toCharArray();
            for (int i = 0; i < L; i++) {
                char orig = arr[i];
                arr[i] = '*';
                String key = new String(arr);
                buckets.computeIfAbsent(key, k -> new ArrayList<>()).add(w);
                arr[i] = orig;
            }
        }
        Deque<String> q = new ArrayDeque<>();
        Deque<Integer> dq = new ArrayDeque<>();
        q.add(beginWord);
        dq.add(1);
        Set<String> seen = new HashSet<>();
        seen.add(beginWord);
        while (!q.isEmpty()) {
            String w = q.poll();
            int d = dq.poll();
            if (w.equals(endWord)) return d;
            char[] arr = w.toCharArray();
            for (int i = 0; i < L; i++) {
                char orig = arr[i];
                arr[i] = '*';
                String key = new String(arr);
                arr[i] = orig;
                List<String> nbrs = buckets.get(key);
                if (nbrs == null) continue;
                for (String nx : nbrs) {
                    if (seen.add(nx)) {
                        q.add(nx);
                        dq.add(d + 1);
                    }
                }
                nbrs.clear(); // optional dedupe optimization
            }
        }
        return 0;
    }
}

function ladderLength(beginWord: string, endWord: string, wordList: string[]): number {
    const dict = new Set<string>(wordList);
    if (!dict.has(endWord)) return 0;
    const L = beginWord.length;
    const buckets = new Map<string, string[]>();
    for (const w of dict) {
        for (let i = 0; i < L; i++) {
            const key = w.slice(0, i) + '*' + w.slice(i + 1);
            if (!buckets.has(key)) buckets.set(key, []);
            buckets.get(key)!.push(w);
        }
    }
    let q: [string, number][] = [[beginWord, 1]];
    const seen = new Set<string>([beginWord]);
    while (q.length > 0) {
        const next: [string, number][] = [];
        for (const [w, d] of q) {
            if (w === endWord) return d;
            for (let i = 0; i < L; i++) {
                const key = w.slice(0, i) + '*' + w.slice(i + 1);
                const nbrs = buckets.get(key);
                if (!nbrs) continue;
                for (const nx of nbrs) {
                    if (!seen.has(nx)) {
                        seen.add(nx);
                        next.push([nx, d + 1]);
                    }
                }
                buckets.set(key, []); // optional dedupe optimization
            }
        }
        q = next;
    }
    return 0;
}

Editorial#

The pattern-bucket trick reduces neighbor discovery from O(N * L) per node to O(L) lookups plus the size of each bucket. BFS over an unweighted graph yields the shortest hop count by construction. Clearing buckets after consumption avoids revisiting them on later pops.

Complexity#

Time: O(N * L^2) for bucket build, comparable for BFS.
Space: O(N * L) for buckets and queue.

Problem#

Examples#

Constraints#

Hints#

Approach#

Solution#

Editorial#

Complexity#

Concept revision#

Keyboard shortcuts

Problem#

Examples#

Constraints#

Hints#

Approach#

Solution#

Editorial#

Complexity#

Concept revision#

Related#