Genomgång av svåra problem: Word Ladder II och Alien Dictionary

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

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