مسئله · رشته‌ها سخت 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 میلی‌ثانیه · $0.0014 ✓ ladder_length('hit', 'cog', ['hot', 'dot', 'dog', 'lot', 'log', 'cog'])مورد انتظار 5 1 میلی‌ثانیه ✓ ladder_length('hit', 'cog', ['hot', 'dot', 'dog', 'lot', 'log'])مورد انتظار 0 <1 میلی‌ثانیه ✓ 1 میلی‌ثانیه✓ 1 میلی‌ثانیه✓ <1 میلی‌ثانیه✓ 1 میلی‌ثانیه✓ 1 میلی‌ثانیه✓ 1 میلی‌ثانیه⏱ 9 میلی‌ثانیه⏱ 13 میلیثانیهکد
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 میلی‌ثانیه · $0.0016 ✓ ladder_length('hit', 'cog', ['hot', 'dot', 'dog', 'lot', 'log', 'cog'])مورد انتظار 5 <1 میلی‌ثانیه ✓ ladder_length('hit', 'cog', ['hot', 'dot', 'dog', 'lot', 'log'])مورد انتظار 0 <1 میلی‌ثانیه ✓ <1 میلی‌ثانیه✓ <1 میلی‌ثانیه✓ <1 میلی‌ثانیه✓ <1 میلی‌ثانیه✓ <1 میلی‌ثانیه✓ <1 میلی‌ثانیه⏱ 96 میلی‌ثانیه⏱ 111 میلیثانیهکد
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 میلی‌ثانیه · $0.0001 ✓ ladder_length('hit', 'cog', ['hot', 'dot', 'dog', 'lot', 'log', 'cog'])مورد انتظار 5 <1 میلی‌ثانیه ✓ ladder_length('hit', 'cog', ['hot', 'dot', 'dog', 'lot', 'log'])مورد انتظار 0 <1 میلی‌ثانیه ✓ <1 میلی‌ثانیه✓ <1 میلی‌ثانیه✓ <1 میلی‌ثانیه✓ <1 میلی‌ثانیه✓ <1 میلی‌ثانیه✓ 1 میلی‌ثانیه⏱ 106 میلی‌ثانیه⏱ 103 میلیثانیهکد
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 میلی‌ثانیه · $0.0002 ✓ ladder_length('hit', 'cog', ['hot', 'dot', 'dog', 'lot', 'log', 'cog'])مورد انتظار 5 <1 میلی‌ثانیه ✓ ladder_length('hit', 'cog', ['hot', 'dot', 'dog', 'lot', 'log'])مورد انتظار 0 <1 میلی‌ثانیه ✓ <1 میلی‌ثانیه✓ <1 میلی‌ثانیه✓ <1 میلی‌ثانیه✓ <1 میلی‌ثانیه✓ 1 میلی‌ثانیه✓ <1 میلی‌ثانیه⏱ 173 میلی‌ثانیه⏱ 405 میلیثانیهکد
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 · نحوه برگزاری راندها و امتیازدهی ←