困难问题 walkthrough：Word Ladder II 与 Alien Dictionary

困难题为何不同

# 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}')

单词接龙 II：题目描述

# 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]]')

单词接龙 II：BFS 阶段

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}')

单词接龙 II：DFS 回溯阶段

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']))

外星字典：题目描述

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')

外星字典：构建图

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)

外星字典：拓扑排序

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)

处理边界情况：两道题目

# 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 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 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)

建立解决困难题的信心

# 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')

快速检查

课程回顾