Hard Problem Walkthroughs: Word Ladder II and Alien Dictionary
Tackle two hard problems end-to-end — word-ladder-II with BFS + backtracking and alien-dictionary with topological sort — with full explanation.
Why Hard Problems Are Different
Hard LeetCode problems differ from medium problems in two key ways: (1) they require combining two or more algorithmic techniques, and (2) the optimal solution is often non-obvious from the problem statement alone — you must see through the surface description to the underlying graph or DP structure. Word Ladder II and Alien Dictionary are canonical hard problems that appear in FAANG interviews repeatedly.
The approach for hard problems: do not try to see the complete solution upfront. Instead, break it into sub-problems, identify the structure of each sub-problem, solve each independently, then connect them. This modular thinking is the key to hard problem solving under pressure.
# Hard problem meta-strategy
strategy = [
'1. Read the problem 2x — hard problems often have subtle constraints',
'2. Model it as a known structure: graph? DP table? sorted order?',
'3. Break into sub-problems: separate the graph-building from the traversal',
'4. Solve sub-problems in order, verifying each before connecting',
'5. Handle the edge case where no solution exists (empty result, -1, [])',
'6. Optimise only after the correct but slow solution works',
]
print('Hard problem meta-strategy:')
for step in strategy:
print(f' {step}')Word Ladder II: Problem Statement
Word Ladder II (LeetCode 126): Given a start word, an end word, and a word list, find all shortest transformation sequences from start to end. Each step transforms exactly one character, and each intermediate word must be in the word list. This is strictly harder than Word Ladder I (which finds just one shortest path) because you must enumerate all optimal paths.
Example: beginWord='hit', endWord='cog', wordList=['hot','dot','dog','lot','log','cog'] → [['hit','hot','dot','dog','cog'],['hit','hot','lot','log','cog']]. Both have length 5.
# Word Ladder II problem breakdown
begin_word = 'hit'
end_word = 'cog'
word_list = ['hot','dot','dog','lot','log','cog']
# What we need:
# 1. Build a graph: word -> set of words that differ by one character
# 2. BFS to find the MINIMUM number of steps (shortest path distance)
# 3. DFS/backtracking to enumerate ALL paths of that minimum length
# Key insight: BFS finds shortest distance; DFS reconstructs all shortest paths
# Two-phase approach:
print('Phase 1: BFS from begin_word to find min distance to each word')
print('Phase 2: DFS/backtrack from end_word using only edges that decrease distance')
print()
print(f'Input: {begin_word} -> {end_word}')
print(f'Word list: {word_list}')
print('Expected: [[hit,hot,dot,dog,cog],[hit,hot,lot,log,cog]]')All lessons in this course
- Pattern Recognition Cheat Sheet
- Timed Mock Interview: Easy and Medium Problems
- Handling Edge Cases and Interviewee Communication
- Hard Problem Walkthroughs: Word Ladder II and Alien Dictionary