โจทย์ · สตริง ยาก 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 · วิธีจัดการแข่งขันและการคิดคะแนน →