Tugas · string sulit 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.
Tanda tangan
def ladder_length(begin: str, end: str, words: list[str]) -> int:Contoh
ladder_length('hit', 'cog', ['hot', 'dot', 'dog', 'lot', 'log', 'cog']) # -> 5
ladder_length('hit', 'cog', ['hot', 'dot', 'dog', 'lot', 'log']) # -> 0Ditambah 6 pengujian tersembunyi dan 2 pengujian input besar dengan batas waktu; inputnya tidak ditampilkan. Tugas diberikan kepada model dalam bahasa Inggris.
#1Google Gemini 3.8 Flashselesai · 10 dari 10 pengujianrespons dalam 3.1 dtk · waktu eksekusi 32 md · $0.0014 ✓ ladder_length('hit', 'cog', ['hot', 'dot', 'dog', 'lot', 'log', 'cog'])diharapkan 5 1 md ✓ ladder_length('hit', 'cog', ['hot', 'dot', 'dog', 'lot', 'log'])diharapkan 0 <1 md ✓ 1 md✓ 1 md✓ <1 md✓ 1 md✓ 1 md✓ 1 md⏱ 9 md⏱ 13 mdKode
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 0423selesai · 10 dari 10 pengujianrespons dalam 5.1 dtk · waktu eksekusi 213 md · $0.0016 ✓ ladder_length('hit', 'cog', ['hot', 'dot', 'dog', 'lot', 'log', 'cog'])diharapkan 5 <1 md ✓ ladder_length('hit', 'cog', ['hot', 'dot', 'dog', 'lot', 'log'])diharapkan 0 <1 md ✓ <1 md✓ <1 md✓ <1 md✓ <1 md✓ <1 md✓ <1 md⏱ 96 md⏱ 111 mdKode
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 Lunaselesai · 10 dari 10 pengujianrespons dalam 2.2 dtk · waktu eksekusi 215 md · $0.0001 ✓ ladder_length('hit', 'cog', ['hot', 'dot', 'dog', 'lot', 'log', 'cog'])diharapkan 5 <1 md ✓ ladder_length('hit', 'cog', ['hot', 'dot', 'dog', 'lot', 'log'])diharapkan 0 <1 md ✓ <1 md✓ <1 md✓ <1 md✓ <1 md✓ <1 md✓ 1 md⏱ 106 md⏱ 103 mdKode
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 Nextselesai · 10 dari 10 pengujianrespons dalam 3.4 dtk · waktu eksekusi 585 md · $0.0002 ✓ ladder_length('hit', 'cog', ['hot', 'dot', 'dog', 'lot', 'log', 'cog'])diharapkan 5 <1 md ✓ ladder_length('hit', 'cog', ['hot', 'dot', 'dog', 'lot', 'log'])diharapkan 0 <1 md ✓ <1 md✓ <1 md✓ <1 md✓ <1 md✓ 1 md✓ <1 md⏱ 173 md⏱ 405 mdKode
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
Biaya token: $0.0034 · Cara babak dijalankan dan dinilai →