編碼挑戰是提高程式設計技能、參與社群和學習新技術的絕佳方式。在這篇文章中，我們將提出一個編碼挑戰，討論解決該問題的各種方法，並邀請讀者在評論中分享他們的解決方案。讓我們潛入吧！
問題：
給定一個字串 s，找出 s 中最長的回文子字串。回文是向後讀與向前讀相同的字串。
範例：
Input: s = "babad" Output: "bab" Note: "aba" is also a valid answer.
約束：
在進入程式碼之前，請確保您已理解問題。回文子字串是向後讀與向前讀相同的字元序列。我們的目標是找到給定字串 s 中最長的子字串。
有多種方法可以解決這個問題。我們將討論三種方法：
蠻力方法涉及檢查所有可能的子字串並確定它們是否是回文。這種方法很簡單，但對於大字串來說效率不高。
def longest_palindrome_brute_force(s):
def is_palindrome(sub):
return sub == sub[::-1]
n = len(s)
longest = ""
for i in range(n):
for j in range(i, n):
if is_palindrome(s[i:j+1]) and len(s[i:j+1]) > len(longest):
longest = s[i:j+1]
return longest
print(longest_palindrome_brute_force("babad")) # Output: "bab" or "aba"
這種方法涉及圍繞每個字元（以及字元之間）進行擴展以找到最長的回文。它比蠻力更有效率。
def longest_palindrome_expand_center(s):
def expand_around_center(left, right):
while left >= 0 and right < len(s) and s[left] == s[right]:
left -= 1
right += 1
return s[left+1:right]
longest = ""
for i in range(len(s)):
# Odd length palindromes
odd_palindrome = expand_around_center(i, i)
if len(odd_palindrome) > len(longest):
longest = odd_palindrome
# Even length palindromes
even_palindrome = expand_around_center(i, i+1)
if len(even_palindrome) > len(longest):
longest = even_palindrome
return longest
print(longest_palindrome_expand_center("babad")) # Output: "bab" or "aba"
動態規劃方法使用表格來儲存子字串是否為回文，從而獲得高效的解決方案。
def longest_palindrome_dp(s):
n = len(s)
if n == 0:
return ""
dp = [[False] * n for _ in range(n)]
start, max_length = 0, 1
for i in range(n):
dp[i][i] = True
for length in range(2, n+1):
for i in range(n-length+1):
j = i + length - 1
if s[i] == s[j]:
if length == 2 or dp[i+1][j-1]:
dp[i][j] = True
if length > max_length:
start = i
max_length = length
return s[start:start+max_length]
print(longest_palindrome_dp("babad")) # Output: "bab" or "aba"
以上是程式設計挑戰：透過解決問題參與與學習的詳細內容。更多資訊請關注PHP中文網其他相關文章！
