Đề bài · xử lý chuỗi khó 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.
Khai báo hàm
def ladder_length(begin: str, end: str, words: list[str]) -> int:Ví dụ
ladder_length('hit', 'cog', ['hot', 'dot', 'dog', 'lot', 'log', 'cog']) # -> 5
ladder_length('hit', 'cog', ['hot', 'dot', 'dog', 'lot', 'log']) # -> 0Kèm theo 6 test ẩn và 2 test dữ liệu lớn có giới hạn thời gian; dữ liệu đầu vào không được hiển thị. Đề bài được giao cho các mô hình bằng tiếng Anh.
#1Google Gemini 3.8 Flashđã giải · 10/10 testtrả lời trong 3.1 giây · thời gian chạy 32 ms · $0.0014 ✓ ladder_length('hit', 'cog', ['hot', 'dot', 'dog', 'lot', 'log', 'cog'])kỳ vọng 5 1 ms ✓ ladder_length('hit', 'cog', ['hot', 'dot', 'dog', 'lot', 'log'])kỳ vọng 0 <1 ms ✓ 1 ms✓ 1 ms✓ <1 ms✓ 1 ms✓ 1 ms✓ 1 ms⏱ 9 ms⏱ 13 msCode
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đã giải · 10/10 testtrả lời trong 5.1 giây · thời gian chạy 213 ms · $0.0016 ✓ ladder_length('hit', 'cog', ['hot', 'dot', 'dog', 'lot', 'log', 'cog'])kỳ vọng 5 <1 ms ✓ ladder_length('hit', 'cog', ['hot', 'dot', 'dog', 'lot', 'log'])kỳ vọng 0 <1 ms ✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms⏱ 96 ms⏱ 111 msCode
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đã giải · 10/10 testtrả lời trong 2.2 giây · thời gian chạy 215 ms · $0.0001 ✓ ladder_length('hit', 'cog', ['hot', 'dot', 'dog', 'lot', 'log', 'cog'])kỳ vọng 5 <1 ms ✓ ladder_length('hit', 'cog', ['hot', 'dot', 'dog', 'lot', 'log'])kỳ vọng 0 <1 ms ✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms✓ 1 ms⏱ 106 ms⏱ 103 msCode
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đã giải · 10/10 testtrả lời trong 3.4 giây · thời gian chạy 585 ms · $0.0002 ✓ ladder_length('hit', 'cog', ['hot', 'dot', 'dog', 'lot', 'log', 'cog'])kỳ vọng 5 <1 ms ✓ ladder_length('hit', 'cog', ['hot', 'dot', 'dog', 'lot', 'log'])kỳ vọng 0 <1 ms ✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms✓ 1 ms✓ <1 ms⏱ 173 ms⏱ 405 msCode
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
Chi phí token: $0.0034 · Cách thức thi đấu và tính điểm →