Défis de codage : s'engager et apprendre grâce à la résolution de problèmes

Défis de codage : s'engager et apprendre grâce à la résolution de problèmes

Les défis de codage sont un moyen fantastique d'améliorer vos compétences en programmation, de vous engager dans une communauté et d'apprendre de nouvelles techniques. Dans cet article de blog, nous présenterons un défi de codage, discuterons de différentes approches pour le résoudre et inviterons les lecteurs à partager leurs solutions dans les commentaires. Allons-y !

Défi : trouver la sous-chaîne palindromique la plus longue

Problème :
Étant donné une chaîne s, recherchez la sous-chaîne palindromique la plus longue de s. Un palindrome est une chaîne qui se lit de la même manière vers l'arrière et vers l'avant.

Exemple :

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

Contraintes :

• 1 <= s.length <= 1000
• s se compose uniquement de chiffres et de lettres anglaises.

Veuillez partager vos solutions avec des approches créatives utilisant différents langages de programmation.

Guide étape par étape pour résoudre le défi

Étape 1 : Comprendre le problème

Avant de vous lancer dans le code, assurez-vous de bien comprendre le problème. Une sous-chaîne palindromique est une séquence de caractères qui se lit de la même manière vers l'arrière et vers l'avant. Notre objectif est de trouver la sous-chaîne la plus longue dans la chaîne s donnée.

Étape 2 : Planifiez votre approche

Il existe plusieurs façons de résoudre ce problème. Nous discuterons de trois approches :

1. Force Brute
2. Développez-vous autour du centre
3. Programmation dynamique

Étape 3 : Mettre en œuvre l’approche par force brute

L'approche par force brute consiste à vérifier toutes les sous-chaînes possibles et à déterminer si ce sont des palindromes. Cette méthode est simple mais peu efficace pour les grandes chaînes.

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"




<h4>
  
  
  Étape 4 : Mettre en œuvre l’approche d’expansion autour du centre
</h4>

<p>Cette approche consiste à s'étendre autour de chaque personnage (et entre les personnages) pour trouver le palindrome le plus long. C'est plus efficace que la force brute.<br>
</p>

<pre class="brush:php;toolbar:false">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"

Étape 5 : Mettre en œuvre l’approche de programmation dynamique

L'approche de programmation dynamique utilise une table pour stocker si une sous-chaîne est un palindrome, conduisant à une solution efficace.

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"

Essayez d'optimiser les algorithmes.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!