Approach: treat words as nodes; edges connect words differing by one letter. Incrementally build components: (1) dictionary preprocessing, (2) neighbor generation, (3) BFS traversal with early exit, (4) optimization: bidirectional BFS.Dictionary preprocessing- Build a set for O(1) lookups and a wildcard map: for each word, for each position replace char with '*' -> map["h*t"] = [hot, hit,...]. This speeds neighbor lookup.- Time: O(N * L) to build (N words, length L). Space: O(N * L) keys total length.Neighbor generation- Using wildcard map: for word, generate L patterns and union map[pattern] lists (excluding self). Cost per word: O(L * avg_bucket_size).- Alternative: try 26 substitutions per position => O(26L) checks against set.BFS traversal with early exit (single-direction)- Standard queue, visited set, level tracking. Stop when target found; return distance or path.- Pseudocode (single-direction):python
from collections import deque, defaultdict
def preprocess(word_list):
L = len(next(iter(word_list)))
wildcard = defaultdict(list)
for w in word_list:
for i in range(L):
wildcard[w[:i] + '*' + w[i+1:]].append(w)
return wildcard
def bfs_shortest(begin, end, word_list):
word_set = set(word_list)
if end not in word_set: return 0
wildcard = preprocess(word_set | {begin})
q = deque([(begin,1)])
visited = {begin}
L = len(begin)
while q:
word, dist = q.popleft()
for i in range(L):
for nei in wildcard[word[:i] + '*' + word[i+1:]]:
if nei == end: return dist+1
if nei not in visited:
visited.add(nei)
q.append((nei, dist+1))
return 0
python
def bidirectional(begin, end, word_list):
word_set = set(word_list)
if end not in word_set: return 0
wildcard = preprocess(word_set | {begin})
L = len(begin)
front, back = {begin}, {end}
visited_front, visited_back = {begin:1}, {end:1}
dist = 1
while front and back:
if len(front) > len(back):
front, back = back, front
visited_front, visited_back = visited_back, visited_front
next_front = set()
for w in front:
for i in range(L):
for nei in wildcard[w[:i] + '*' + w[i+1:]]:
if nei in visited_back:
return visited_front[w] + visited_back[nei]
if nei not in visited_front:
visited_front[nei] = visited_front[w] + 1
next_front.add(nei)
front = next_front
return 0
