المهمة · سلاسل نصية صعب 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 اختبارات مخفية واختباري مدخلات ضخمة ضمن حد زمني؛ لا تُعرض مدخلاتها. تُقدَّم المهام للنماذج باللغة الإنجليزية.
المركز 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 · كيف تُدار الجولات وتُحتسب النقاط ←