課題 · 文字列上級 Python ·

Word ladder

Turn the word begin into end by changing one letter at a time; every word after begin, including end, must be in words. Return the number of words in the shortest such sequence, counting both begin and end, or 0 if there is none. If begin equals end, return 1. All words have the same length and use lowercase letters. Up to 15,000 words.

シグネチャ

def ladder_length(begin: str, end: str, words: list[str]) -> int:

入力例

ladder_length('hit', 'cog', ['hot', 'dot', 'dog', 'lot', 'log', 'cog'])  # -> 5
ladder_length('hit', 'cog', ['hot', 'dot', 'dog', 'lot', 'log'])  # -> 0

その他、入力値が非公開の6個の非公開テストおよび制限時間付きの2個の大規模入力テストがあります。モデルへの課題は英語で出題されます。

#1Google Gemini 3.8 Flash正解 · 10 / 10 件のテストにパス回答時間 3.1 秒 · 実行時間 32 ms · $0.0014

✓	ladder_length('hit', 'cog', ['hot', 'dot', 'dog', 'lot', 'log', 'cog'])期待値 5	1 ms
✓	ladder_length('hit', 'cog', ['hot', 'dot', 'dog', 'lot', 'log'])期待値 0	<1 ms

✓ 1 ms✓ 1 ms✓ <1 ms✓ 1 ms✓ 1 ms✓ 1 ms⏱ 9 ms⏱ 13 ms

コード

def ladder_length(begin: str, end: str, words: list[str]) -> int:
    if begin == end:
        return 1
    
    word_set = set(words)
    if end not in word_set:
        return 0
    
    if begin in word_set:
        word_set.remove(begin)
        
    front = {begin}
    back = {end}
    word_set.discard(end)
    
    length = 1
    word_len = len(begin)
    alphabet = 'abcdefghijklmnopqrstuvwxyz'
    
    while front and back:
        if len(front) > len(back):
            front, back = back, front
            
        next_front = set()
        for word in front:
            for i in range(word_len):
                orig_char = word[i]
                for c in alphabet:
                    if c == orig_char:
                        continue
                    nxt = word[:i] + c + word[i+1:]
                    if nxt in back:
                        return length + 1
                    if nxt in word_set:
                        next_front.add(nxt)
                        word_set.remove(nxt)
                        
        length += 1
        front = next_front
        
    return 0

#2DeepSeek V4 Pro 0423正解 · 10 / 10 件のテストにパス回答時間 5.1 秒 · 実行時間 213 ms · $0.0016

✓	ladder_length('hit', 'cog', ['hot', 'dot', 'dog', 'lot', 'log', 'cog'])期待値 5	<1 ms
✓	ladder_length('hit', 'cog', ['hot', 'dot', 'dog', 'lot', 'log'])期待値 0	<1 ms

✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms⏱ 96 ms⏱ 111 ms

コード

from collections import deque

def ladder_length(begin: str, end: str, words: list[str]) -> int:
    if begin == end:
        return 1

    word_set = set(words)
    if end not in word_set:
        return 0

    # Preprocess words into a pattern-based adjacency to speed up neighbor lookup
    # For each word, generate all patterns by replacing each character with '*'
    # Map pattern to list of words that match it
    L = len(begin)
    pattern_map = {}
    for word in word_set:
        for i in range(L):
            pattern = word[:i] + '*' + word[i+1:]
            pattern_map.setdefault(pattern, []).append(word)
    # Also add begin to the pattern map, but only for neighbor generation
    for i in range(L):
        pattern = begin[:i] + '*' + begin[i+1:]
        pattern_map.setdefault(pattern, []).append(begin)

    # BFS from begin
    queue = deque()
    queue.append((begin, 1))
    visited = set()
    visited.add(begin)

    while queue:
        current, dist = queue.popleft()
        for i in range(L):
            pattern = current[:i] + '*' + current[i+1:]
            for neighbor in pattern_map.get(pattern, []):
                if neighbor == end:
                    return dist + 1
                if neighbor not in visited:
                    visited.add(neighbor)
                    queue.append((neighbor, dist + 1))
            # Clear pattern to avoid redundant lookups
            pattern_map[pattern] = []

    return 0

#2OpenAI GPT-6 Luna正解 · 10 / 10 件のテストにパス回答時間 2.2 秒 · 実行時間 215 ms · $0.0001

✓	ladder_length('hit', 'cog', ['hot', 'dot', 'dog', 'lot', 'log', 'cog'])期待値 5	<1 ms
✓	ladder_length('hit', 'cog', ['hot', 'dot', 'dog', 'lot', 'log'])期待値 0	<1 ms

✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms✓ 1 ms⏱ 106 ms⏱ 103 ms

コード

from collections import defaultdict, deque

def ladder_length(begin: str, end: str, words: list[str]) -> int:
    if begin == end:
        return 1

    word_set = set(words)
    if end not in word_set:
        return 0

    word_set.add(begin)
    buckets = defaultdict(list)
    length = len(begin)

    for word in word_set:
        for i in range(length):
            buckets[word[:i] + "*" + word[i + 1:]].append(word)

    queue = deque([(begin, 1)])
    visited = {begin}

    while queue:
        word, distance = queue.popleft()
        for i in range(length):
            pattern = word[:i] + "*" + word[i + 1:]
            for neighbor in buckets[pattern]:
                if neighbor == end:
                    return distance + 1
                if neighbor not in visited:
                    visited.add(neighbor)
                    queue.append((neighbor, distance + 1))
            buckets[pattern] = []

    return 0

#4Qwen3 Coder Next正解 · 10 / 10 件のテストにパス回答時間 3.4 秒 · 実行時間 585 ms · $0.0002

✓	ladder_length('hit', 'cog', ['hot', 'dot', 'dog', 'lot', 'log', 'cog'])期待値 5	<1 ms
✓	ladder_length('hit', 'cog', ['hot', 'dot', 'dog', 'lot', 'log'])期待値 0	<1 ms

✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms✓ 1 ms✓ <1 ms⏱ 173 ms⏱ 405 ms

コード

from collections import deque

def ladder_length(begin: str, end: str, words: list[str]) -> int:
    # If begin equals end, return 1
    if begin == end:
        return 1
    
    # Convert words to a set for O(1) lookups
    word_set = set(words)
    
    # If end is not in words, no valid sequence exists
    if end not in word_set:
        return 0
    
    # BFS setup
    queue = deque([(begin, 1)])
    visited = {begin}
    
    # Generate all possible next words by changing one letter at a time
    while queue:
        current_word, length = queue.popleft()
        
        # Try changing each position in the word
        for i in range(len(current_word)):
            for c in 'abcdefghijklmnopqrstuvwxyz':
                if c == current_word[i]:
                    continue
                
                new_word = current_word[:i] + c + current_word[i+1:]
                
                if new_word == end:
                    return length + 1
                
                if new_word in word_set and new_word not in visited:
                    visited.add(new_word)
                    queue.append((new_word, length + 1))
    
    return 0

トークンコスト: $0.0034 · 対戦の進行と評価方法について →