程式設計挑戰：透過解決問題參與與學習

程式設計挑戰：透過解決問題參與與學習

編碼挑戰是提高程式設計技能、參與社群和學習新技術的絕佳方式。在這篇文章中，我們將提出一個編碼挑戰，討論解決該問題的各種方法，並邀請讀者在評論中分享他們的解決方案。讓我們潛入吧！

挑戰：找出最長的回文子字串

問題：
給定一個字串 s，找出 s 中最長的回文子字串。回文是向後讀與向前讀相同的字串。

範例：

Input: s = "babad"
Output: "bab"
Note: "aba" is also a valid answer.

約束：

• 1
• s 僅由數字和英文字母組成。

請使用不同的程式語言以創意的方法分享您的解決方案。

解決挑戰的逐步指南

第 1 步：了解問題

在進入程式碼之前，請確保您已理解問題。回文子字串是向後讀與向前讀相同的字元序列。我們的目標是找到給定字串 s 中最長的子字串。

第 2 步：規劃你的方法

有多種方法可以解決這個問題。我們將討論三種方法：

1. 暴力破解
2. 圍繞中心展開
3. 動態規劃

第 3 步：實施暴力方法

蠻力方法涉及檢查所有可能的子字串並確定它們是否是回文。這種方法很簡單，但對於大字串來說效率不高。

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"

步驟 4：實施圍繞中心擴展方法

這種方法涉及圍繞每個字元（以及字元之間）進行擴展以找到最長的回文。它比蠻力更有效率。

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"

第 5 步：實施動態規劃方法

動態規劃方法使用表格來儲存子字串是否為回文，從而獲得高效的解決方案。

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中文網其他相關文章！