Разбор сложных задач: «Лестница слов II» и «Инопланетный словарь»

Чем сложные задачи отличаются

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

Быстрая проверка

Итоги урока