コーディングの課題: 問題解決を通じて取り組み、学習する

コーディングの課題: 問題解決を通じて取り組み、学習する

コーディング チャレンジは、プログラミング スキルを向上させ、コミュニティに参加し、新しいテクニックを学ぶための素晴らしい方法です。このブログ投稿では、コーディングの課題を提示し、それを解決するためのさまざまなアプローチについて説明し、読者にコメントで解決策を共有するよう呼びかけます。飛び込んでみましょう!

チャレンジ: 最長の回文部分文字列を見つけてください

問題:
文字列 s が与えられた場合、s 内の最長の回文部分文字列を見つけます。回文は、後ろから読んでも前から読んでも同じように読める文字列です。

例:

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

制約:

• 1
• s は数字と英字のみで構成されます。

さまざまなプログラミング言語を使用した創造的なアプローチでソリューションを共有してください。

課題を解決するためのステップバイステップガイド

ステップ 1: 問題を理解する

コードに取り掛かる前に、問題を必ず理解してください。回文部分文字列は、前方から見ても前方から見ても同じように読める一連の文字です。私たちの目標は、指定された文字列 s 内でそのような最長の部分文字列を見つけることです。

ステップ 2: アプローチを計画する

この問題を解決するにはいくつかの方法があります。 3 つのアプローチについて説明します。

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 中国語 Web サイトの他の関連記事を参照してください。