Đề bài · xử lý chuỗi khó Python ·
Longest palindromic substring
Return the longest substring of s that reads the same backwards. If several have that length, return the leftmost. s has lowercase letters only and can be up to 200,000 characters long.
Khai báo hàm
def longest_palindrome(s: str) -> str:Ví dụ
longest_palindrome('babad') # -> 'bab'
longest_palindrome('cbbd') # -> 'bb'
longest_palindrome('') # -> ''Kèm theo 9 test ẩn và 3 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.
#1Anthropic Claude Sonnet 5.5đã giải · 15/15 testtrả lời trong 6.0 giây · thời gian chạy 806 ms · $0.0090 ✓ longest_palindrome('babad')kỳ vọng 'bab' <1 ms ✓ longest_palindrome('cbbd')kỳ vọng 'bb' <1 ms ✓ longest_palindrome('')kỳ vọng '' <1 ms ✓ <1 ms✓ <1 ms✓ <1 ms✓ 1 ms✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms⏱ 306 ms⏱ 265 ms⏱ 226 msCode
def longest_palindrome(s: str) -> str: if not s: return '' t = '^#' + '#'.join(s) + '#$' n = len(t) p = [0] * n c = r = 0 best = 0 bi = 0 for i in range(1, n - 1): if i < r: k = p[2 * c - i] m = r - i pi = k if k < m else m else: pi = 0 while t[i + pi + 1] == t[i - pi - 1]: pi += 1 p[i] = pi if i + pi > r: c = i r = i + pi if pi > best: best = pi bi = i start = (bi - best) // 2 return s[start:start + best]#2OpenAI GPT-6.1 Terrađã giải · 15/15 testtrả lời trong 6.1 giây · thời gian chạy 1.1 giây · $0.0023 ✓ longest_palindrome('babad')kỳ vọng 'bab' <1 ms ✓ longest_palindrome('cbbd')kỳ vọng 'bb' 1 ms ✓ longest_palindrome('')kỳ vọng '' <1 ms ✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms✓ 2 ms✓ 1 ms✓ <1 ms✓ 1 ms✓ <1 ms⏱ 427 ms⏱ 322 ms⏱ 329 msCode
def longest_palindrome(s: str) -> str: n = len(s) if n < 2: return s best_start = 0 best_len = 1 odd = [0] * n left, right = 0, -1 for i in range(n): k = 1 if i > right else min(odd[left + right - i], right - i + 1) while i - k >= 0 and i + k < n and s[i - k] == s[i + k]: k += 1 odd[i] = k length = 2 * k - 1 start = i - k + 1 if length > best_len or (length == best_len and start < best_start): best_len, best_start = length, start if i + k - 1 > right: left, right = i - k + 1, i + k - 1 even = [0] * n left, right = 0, -1 for i in range(n): k = 0 if i > right else min(even[left + right - i + 1], right - i + 1) while i - k - 1 >= 0 and i + k < n and s[i - k - 1] == s[i + k]: k += 1 even[i] = k length = 2 * k start = i - k if length > best_len or (length == best_len and start < best_start): best_len, best_start = length, start if i + k - 1 > right: left, right = i - k, i + k - 1 return s[best_start:best_start + best_len]#2Google Gemini 3.8 Flashđã giải · 15/15 testtrả lời trong 11 giây · thời gian chạy 1.2 giây · $0.0032 ✓ longest_palindrome('babad')kỳ vọng 'bab' <1 ms ✓ longest_palindrome('cbbd')kỳ vọng 'bb' <1 ms ✓ longest_palindrome('')kỳ vọng '' <1 ms ✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms✓ 1 ms✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms⏱ 428 ms⏱ 389 ms⏱ 331 msCode
def longest_palindrome(s: str) -> str: if not s: return "" t = "^#" + "#".join(s) + "#$" n = len(t) p = [0] * n c = 0 r = 0 max_len = 0 best_start = 0 for i in range(1, n - 1): i_mirror = 2 * c - i if r > i: p[i] = min(r - i, p[i_mirror]) else: p[i] = 0 while t[i + 1 + p[i]] == t[i - 1 - p[i]]: p[i] += 1 if i + p[i] > r: c = i r = i + p[i] length = p[i] if length > max_len: max_len = length best_start = (i - length) // 2 return s[best_start : best_start + max_len]#2Qwen3.8 Max (0902)đã giải · 15/15 testtrả lời trong 23 giây · thời gian chạy 1.4 giây · $0.0074 ✓ longest_palindrome('babad')kỳ vọng 'bab' <1 ms ✓ longest_palindrome('cbbd')kỳ vọng 'bb' <1 ms ✓ longest_palindrome('')kỳ vọng '' <1 ms ✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms✓ 1 ms✓ <1 ms✓ <1 ms✓ <1 ms⏱ 441 ms⏱ 444 ms⏱ 467 msCode
def longest_palindrome(s: str) -> str: if not s: return '' # Manacher's algorithm t = '#' + '#'.join(s) + '#' n = len(t) P = [0] * n center = 0 right = 0 best_center = 0 best_len = 0 for i in range(n): mirror = 2 * center - i if i < right: P[i] = min(right - i, P[mirror]) while i - P[i] - 1 >= 0 and i + P[i] + 1 < n and t[i - P[i] - 1] == t[i + P[i] + 1]: P[i] += 1 if i + P[i] > right: center = i right = i + P[i] if P[i] > best_len: best_len = P[i] best_center = i start = (best_center - best_len) // 2 return s[start:start + best_len]
Chi phí token: $0.02 · Cách thức thi đấu và tính điểm →