from collections import defaultdict, deque
 
def ladder_length(beginWord, endWord, wordList):
    wordSet = set(wordList)
    if endWord not in wordSet:
        return 0
 
    L = len(beginWord)
    patterns = defaultdict(list)             # pattern -> words matching it
    for w in wordSet:
        for i in range(L):
            patterns[w[:i] + '*' + w[i+1:]].append(w)
 
    visited = {beginWord}
    queue = deque([(beginWord, 1)])
    while queue:
        word, steps = queue.popleft()
        if word == endWord:
            return steps
        for i in range(L):
            key = word[:i] + '*' + word[i+1:]
            for nei in patterns[key]:
                if nei not in visited:
                    visited.add(nei)
                    queue.append((nei, steps + 1))
            patterns[key] = []               # avoid revisiting this pattern
    return 0

#include <queue>
#include <unordered_map>
#include <unordered_set>
#include <vector>
#include <string>
using namespace std;
 
int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
    unordered_set<string> wordSet(wordList.begin(), wordList.end());
    if (!wordSet.count(endWord)) return 0;
 
    int L = beginWord.size();
    unordered_map<string, vector<string>> patterns;
    for (auto& w : wordSet) {
        for (int i = 0; i < L; i++) {
            string key = w.substr(0, i) + '*' + w.substr(i + 1);
            patterns[key].push_back(w);
        }
    }
 
    unordered_set<string> visited{beginWord};
    queue<pair<string, int>> q;
    q.push({beginWord, 1});
    while (!q.empty()) {
        auto [word, steps] = q.front(); q.pop();
        if (word == endWord) return steps;
        for (int i = 0; i < L; i++) {
            string key = word.substr(0, i) + '*' + word.substr(i + 1);
            for (auto& nei : patterns[key]) {
                if (!visited.count(nei)) {
                    visited.insert(nei);
                    q.push({nei, steps + 1});
                }
            }
            patterns[key].clear();
        }
    }
    return 0;
}

import java.util.*;
 
public int ladderLength(String beginWord, String endWord, List<String> wordList) {
    Set<String> wordSet = new HashSet<>(wordList);
    if (!wordSet.contains(endWord)) return 0;
 
    int L = beginWord.length();
    Map<String, List<String>> patterns = new HashMap<>();
    for (String w : wordSet) {
        for (int i = 0; i < L; i++) {
            String key = w.substring(0, i) + '*' + w.substring(i + 1);
            patterns.computeIfAbsent(key, k -> new ArrayList<>()).add(w);
        }
    }
 
    Set<String> visited = new HashSet<>();
    visited.add(beginWord);
    Deque<Map.Entry<String, Integer>> q = new ArrayDeque<>();
    q.offer(Map.entry(beginWord, 1));
    while (!q.isEmpty()) {
        var cur = q.poll();
        String word = cur.getKey();
        int steps = cur.getValue();
        if (word.equals(endWord)) return steps;
        for (int i = 0; i < L; i++) {
            String key = word.substring(0, i) + '*' + word.substring(i + 1);
            for (String nei : patterns.getOrDefault(key, Collections.emptyList())) {
                if (visited.add(nei)) q.offer(Map.entry(nei, steps + 1));
            }
            patterns.put(key, Collections.emptyList());      // avoid revisiting
        }
    }
    return 0;
}