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.
Hard Problem Walkthroughs: Word Ladder II and Alien Dictionary is a free DSA Interview Prep lesson on CoddyKit — lesson 4 of 4. You can read the complete lesson below for free — then practise it hands-on in the browser with a built-in code editor and a 24/7 AI tutor. It is part of the DSA Interview Prep learning path, one of 4 lessons in the course, and your progress syncs across the web and the CoddyKit app.
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]]')Word Ladder II: BFS Phase
In Phase 1, run BFS level by level from the start word. At each level, we find all neighbours (words differing by one character). We record the level (distance from start) at which each word is first reached. We do NOT stop when we reach the end word — we continue until the end of the level where end_word was found, to ensure we explore all shortest paths.
Crucially, we build a parents dictionary mapping each word to the set of words that can precede it in any shortest path. This is the graph we use in Phase 2 for backtracking.
from collections import defaultdict, deque
def find_parents(begin, end, word_set):
parents = defaultdict(set)
layer = {begin}
found = False
while layer and not found:
next_layer = set()
for word in layer:
for i in range(len(word)):
for c in 'abcdefghijklmnopqrstuvwxyz':
new_word = word[:i] + c + word[i+1:]
if new_word in word_set and new_word not in parents:
next_layer.add(new_word)
parents[new_word].add(word)
if new_word == end:
found = True
layer = next_layer
return parents if found else {}
words = {'hot','dot','dog','lot','log','cog'}
parents = find_parents('hit', 'cog', words)
print('Parents map (which words can precede each word):')
for word, preds in sorted(parents.items()):
print(f' {word}: {preds}')Word Ladder II: DFS Backtracking Phase
In Phase 2, use DFS backtracking from the end word, following the parents map in reverse. We build paths from end to start (then reverse them). When we reach the start word, we have found a complete shortest path. The parents map guarantees all paths found are of minimum length — we cannot 'deviate' to a longer path.
This two-phase approach (BFS for levels, DFS for path reconstruction) is the standard solution and runs in O(n × L × 26) for BFS where n = word list size and L = word length, plus O(K × L) for DFS where K = number of shortest paths.
def find_ladders(beginWord, endWord, wordList):
word_set = set(wordList)
if endWord not in word_set:
return []
# Phase 1: BFS to build parents map
parents = defaultdict(set)
layer = {beginWord}
found = False
visited = {beginWord}
while layer and not found:
next_layer = set()
for word in layer:
for i in range(len(word)):
for c in 'abcdefghijklmnopqrstuvwxyz':
nw = word[:i] + c + word[i+1:]
if nw in word_set and nw not in visited:
next_layer.add(nw)
parents[nw].add(word)
if nw == endWord: found = True
visited |= next_layer
layer = next_layer
# Phase 2: DFS backtrack from endWord to beginWord
result = []
def dfs(word, path):
if word == beginWord:
result.append(path[::-1])
return
for parent in parents[word]:
dfs(parent, path + [parent])
dfs(endWord, [endWord])
return result
print(find_ladders('hit','cog',['hot','dot','dog','lot','log','cog']))Alien Dictionary: Problem Statement
Alien Dictionary (LeetCode 269): given a list of words sorted lexicographically in an alien language, determine the order of characters in that language. Return the character ordering as a string. If no valid ordering exists (contradictory), return empty string.
Example: ['wrt','wrf','er','ett','rftt'] → 'wertf'. By comparing adjacent words: 't' < 'f' (from wrt vs wrf), 'w' < 'e' (from wrt vs er), 'r' < 't' (from er vs ett), 'e' < 'r' (from ett vs rftt). This is a topological sort of these character ordering constraints.
words = ['wrt', 'wrf', 'er', 'ett', 'rftt']
# Compare adjacent pairs to extract ordering:
# wrt vs wrf: first diff at index 2: t < f (t comes before f)
# wrf vs er: first diff at index 0: w < e (w comes before e)
# er vs ett: first diff at index 1: r < t (r comes before t)
# ett vs rftt:first diff at index 0: e < r (e comes before r)
ordering_constraints = [
('t', 'f', 'from wrt vs wrf'),
('w', 'e', 'from wrf vs er'),
('r', 't', 'from er vs ett'),
('e', 'r', 'from ett vs rftt'),
]
print('Ordering constraints extracted from adjacent word pairs:')
for a, b, source in ordering_constraints:
print(f' {a} -> {b} ({source})')
print('\nThis is a directed graph: find topological order = alien alphabet order')Alien Dictionary: Building the Graph
The first step is extracting constraints: compare each adjacent pair of words, find the first differing character, and add a directed edge from the smaller to the larger character. If a word is a prefix of the next word but is longer (e.g., 'abc' before 'ab'), the input is invalid — return empty string immediately.
All characters that appear in the word list are nodes in the graph, even if they have no ordering constraints. These isolated nodes can appear anywhere in the final ordering.
from collections import defaultdict
def build_alien_graph(words):
adj = defaultdict(set) # char -> set of chars that come after it
in_degree = {c: 0 for word in words for c in word}
for i in range(len(words) - 1):
w1, w2 = words[i], words[i+1]
min_len = min(len(w1), len(w2))
found_diff = False
for j in range(min_len):
if w1[j] != w2[j]:
if w2[j] not in adj[w1[j]]: # avoid duplicate edges
adj[w1[j]].add(w2[j])
in_degree[w2[j]] += 1
found_diff = True
break
if not found_diff and len(w1) > len(w2):
return {}, {} # invalid: 'abc' before 'ab'
return adj, in_degree
words = ['wrt', 'wrf', 'er', 'ett', 'rftt']
adj, in_degree = build_alien_graph(words)
print('Adjacency list (directed):', {k: list(v) for k, v in adj.items()})
print('In-degrees:', in_degree)Alien Dictionary: Topological Sort
Once the graph is built, apply Kahn's BFS topological sort: initialise a queue with all characters having in-degree 0 (no prerequisites). Process each character, decrement the in-degree of its successors. When a successor's in-degree reaches 0, enqueue it. Collect characters in processing order — this is the alien alphabetical order.
If the result contains all characters, we have a valid ordering. If fewer characters than expected, there is a cycle — the constraints are contradictory and we return empty string.
from collections import deque, defaultdict
def alien_order(words):
adj = defaultdict(set)
in_degree = {c: 0 for word in words for c in word}
for i in range(len(words) - 1):
w1, w2 = words[i], words[i + 1]
min_len = min(len(w1), len(w2))
found = False
for j in range(min_len):
if w1[j] != w2[j]:
if w2[j] not in adj[w1[j]]:
adj[w1[j]].add(w2[j])
in_degree[w2[j]] += 1
found = True; break
if not found and len(w1) > len(w2):
return '' # invalid: 'abc' before 'ab'
# Kahn's BFS topological sort
queue = deque([c for c in in_degree if in_degree[c] == 0])
result = []
while queue:
c = queue.popleft()
result.append(c)
for neighbor in sorted(adj[c]): # sort for determinism
in_degree[neighbor] -= 1
if in_degree[neighbor] == 0:
queue.append(neighbor)
return ''.join(result) if len(result) == len(in_degree) else ''
print(alien_order(['wrt','wrf','er','ett','rftt'])) # e.g., 'wertf'
print(alien_order(['z','x'])) # 'zx'
print(alien_order(['z','x','z'])) # '' (cycle z->x->z)Handling Edge Cases: Both Problems
Both Word Ladder II and Alien Dictionary have subtle edge cases that cause wrong answers if not handled:
- Word Ladder II: beginWord and endWord are the same (return
[[beginWord]]or length 1). endWord not in wordList (return empty). No path exists (return empty). - Alien Dictionary: duplicate words (extract no constraint). Single word (return all unique chars). Cycle in constraints (return ''). A word is longer prefix of the next word (invalid input, return ''). All characters are isolated (return any order).
# Edge case tests for Word Ladder II
def test_word_ladder_edge_cases():
from collections import defaultdict
def find_ladders(begin, end, word_list):
# [abbreviated implementation for testing]
if end not in word_list: return []
if begin == end: return [[begin]]
return [] # placeholder
tests = [
('hit', 'cog', ['hot','dot','dog','lot','log'], []), # no path (cog missing)
('hit', 'hit', ['hit'], [['hit']]), # begin==end
('a', 'c', ['a','b','c'], [['a','c']]), # short words
]
for begin, end, wl, expected in tests:
result = find_ladders(begin, end, wl)
print(f'{begin}->{end}: result={result}')
# Edge case tests for Alien Dictionary
def test_alien_edge_cases():
from collections import defaultdict, deque
# (using alien_order from previous scene)
tests = [
(['abc', 'ab'], ''), # 'abc' before 'ab' = invalid
(['a'], 'a'), # single word
(['z','z'], 'z'), # duplicate: no constraint
]
print('Alien dictionary edge cases:')
for words, expected in tests:
print(f' {words} -> expected: "{expected}"')
test_word_ladder_edge_cases()
test_alien_edge_cases()Complexity Analysis: Both Problems
Word Ladder II complexity: BFS phase runs O(n × L × 26) where n = words in list, L = word length. For each word at each BFS level, we generate 26L candidate words and check membership in the word set (O(1) per check). DFS phase is O(K × L) where K = number of shortest paths (can be exponential in theory).
Alien Dictionary complexity: Building the graph is O(C) where C = total characters across all words. Topological sort is O(V + E) where V = unique characters, E = ordering constraints. Overall O(C) which is O(total characters in input).
# Complexity analysis for both problems
complexities = [
{
'problem': 'Word Ladder II',
'time': 'O(n * L * 26) BFS + O(K * L) DFS backtracking',
'space': 'O(n * L) for word set + parents map',
'notes': 'K (number of shortest paths) can be exponential in pathological cases',
},
{
'problem': 'Alien Dictionary',
'time': 'O(C) where C = total characters in all words',
'space': 'O(V + E) for adjacency list',
'notes': 'V <= 26 (alphabet), E <= V^2 = 676; often treated as O(C) total',
},
]
for c in complexities:
print(f'{c["problem"]}:')
print(f' Time: {c["time"]}')
print(f' Space: {c["space"]}')
print(f' Notes: {c["notes"]}')
print()Pattern Summary: Two Reusable Templates
Both problems teach reusable patterns. Word Ladder II = BFS for distances + DFS for path reconstruction: this pattern appears whenever you need all shortest paths in an unweighted graph. Build the parent map during BFS, then backtrack from destination to source.
Alien Dictionary = edge extraction + topological sort: this pattern appears whenever you are given a sorted sequence and must infer the underlying ordering rules. Extract directed constraints from adjacent pairs, then apply Kahn's algorithm. Return '' on cycle detection (impossible ordering).
# Pattern templates
print('Template 1: All Shortest Paths in Unweighted Graph')
template_1 = '''
1. BFS from source, recording parents[node] = set of nodes that lead to node
2. Continue each BFS level fully (do not stop at first endNode reach)
3. DFS backtrack from endNode, following parents map
4. Reverse each path found (built end->start, need start->end)
'''
print(template_1)
print('Template 2: Infer Ordering from Sorted Sequence')
template_2 = '''
1. Compare adjacent pairs, extract first differing element as directed constraint
2. Build adjacency list + in-degree map
3. Check for invalid input (prefix longer than successor)
4. Kahn's BFS topological sort
5. If result length < number of nodes => cycle => return invalid
'''
print(template_2)Building Confidence on Hard Problems
Hard problems seem impossible at first but become approachable with the right mental model. The key insights:
- Separate concerns: solve each sub-problem independently before connecting them
- Know your building blocks: BFS/DFS, topological sort, Dijkstra, DP tables — hard problems combine these in non-obvious ways
- Start with examples: trace the problem manually with a small example to discover the underlying structure
- Verify sub-problems: after implementing Phase 1 (graph building), print the graph and verify it manually before proceeding to Phase 2
# Hard problem confidence-building practice plan
practice_plan = [
('Week 1', 'BFS/DFS fundamentals', ['Number of Islands', 'Clone Graph', 'Word Ladder I']),
('Week 2', 'Topological sort', ['Course Schedule I & II', 'Alien Dictionary (easy)']),
('Week 3', 'All-paths problems', ['All Paths to Target', 'Word Ladder II (hard)']),
('Week 4', 'Hard combos', ['Minimum Window Substring', 'Serialize/Deserialize Tree']),
]
print('4-week hard problem practice plan:')
for week, theme, problems in practice_plan:
print(f'\n{week} — {theme}:')
for p in problems:
print(f' - {p}')
print('\nAfter each problem, write:')
print(' 1. The pattern it belongs to')
print(' 2. The 2-3 key sub-problems')
print(' 3. One insight you would not have had before solving it')Quick Check
Test your understanding of Data Structures & Algorithms — Coding Interview Prep concepts from this lesson.
Lesson Recap
In this lesson you learned: Word Ladder II uses BFS to build a parents map of all shortest-path predecessors, then DFS backtracking to enumerate all shortest paths by following parents from end to start, Alien Dictionary extracts directed constraints from adjacent word pairs and applies Kahn's topological sort to order characters, returning empty string on cycle detection, and hard problems decompose into multiple sub-problems — building the graph, finding distances, and reconstructing paths — each solved independently with familiar algorithms. You have now completed the full DSA Interview Prep course. Apply every pattern and technique from this track to your interviews with confidence.
Frequently asked questions
Is the “Hard Problem Walkthroughs: Word Ladder II and Alien Dictionary” lesson free?
Yes — the full text of “Hard Problem Walkthroughs: Word Ladder II and Alien Dictionary” is free to read here on the web, and the DSA Interview Prep course includes 4 lessons in total. To practise it interactively (a built-in code editor and a 24/7 AI tutor) and unlock the rest of the DSA Interview Prep course, upgrade to CoddyKit PRO.
What will I learn in “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. You practise DSA Interview Prep with hands-on code you run directly in the browser, and a 24/7 AI tutor answers your questions as you work through the lesson.
Do I need any experience to start DSA Interview Prep?
No prior experience is required. DSA Interview Prep on CoddyKit is structured for beginners through advanced learners; this is — lesson 4 of 4, so you can start here or from the beginning and move at your own pace.
How long does the “Hard Problem Walkthroughs: Word Ladder II and Alien Dictionary” lesson take?
Most CoddyKit lessons take about 5–10 minutes. Each one is bite-sized and interactive, so you make steady progress and pick up exactly where you left off across the web and the app.
Can I write and run code in this DSA Interview Prep lesson?
Yes. Every DSA Interview Prep lesson includes a built-in code editor, so you write and run real code right in your browser and get instant AI feedback — no local setup required.
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