Palindrome String

Q: Comment vérifier si une chaîne est un palindrome ?

Comparez le premier caractère avec le dernier, le deuxième avec l’avant-dernier, et ainsi de suite vers le milieu. Si une paire diffère, la chaîne n’est pas un palindrome ; si toutes les paires correspondent, elle en est un. Deux indices qui commencent aux deux extrémités et avancent vers l’intérieur permettent de faire cela en un seul parcours.

Q: Peux-tu vérifier si une chaîne est un palindrome sans mémoire supplémentaire ?

Oui. La vérification avec deux pointeurs lit les caractères sur place et ne stocke que deux indices, elle utilise donc un espace supplémentaire de O(1) . Comparer s à son inverse est plus court à écrire, mais crée une deuxième chaîne de n caractères.

Q: Quelle est la complexité temporelle de la vérification d’une chaîne palindrome ?

C'est O(n) pour une chaîne de longueur n . La vérification à deux pointeurs effectue au plus n / 2 comparaisons et s'arrête à la première différence, donc une chaîne dont le premier et le dernier caractère diffèrent est déterminée après une seule comparaison.

Q: Un caractère seul est-il un palindrome ?

Oui. Un caractère se lit de la même façon dans les deux sens, donc la réponse est true . Dans la boucle à deux pointeurs, left et right commencent tous deux à l’index 0, la boucle ne s’exécute jamais et la fonction renvoie true .

DébutantDeux pointeurs Tableaux et chaînes

+10

Une chaîne est un palindrome lorsqu’elle se lit de la même façon de gauche à droite et de droite à gauche, comme level. Écris une fonction qui reçoit une chaîne s composée de lettres minuscules de l’alphabet anglais et renvoie true si s est un palindrome et false sinon.

Fonction

isPalindrome(s: string) → boolean

sstring: la chaîne en minuscules à vérifier
Renvoieboolean: vrai lorsque s se lit de la même façon dans les deux sens

Contraintes

1 ≤ s.length ≤ 5 × 10⁴
s ne contient que des lettres minuscules anglaises (a à z).

Exemples

Entrée: s = "racecar"
Sortie: true
Explication: Comparez de l’extérieur vers l’intérieur : r avec r, a avec a, c avec c. Le e du milieu n’a pas de partenaire et n’en a pas besoin, donc la réponse est true.

Entrée: s = "abba"
Sortie: true
Explication: Avec une longueur paire, chaque lettre a une partenaire : les deux a correspondent et les deux b correspondent, donc la réponse est true.

Entrée: s = "coddy"
Sortie: false
Explication: La première lettre c et la dernière lettre y sont déjà différentes, donc coddy n’est pas un palindrome et la réponse est false.

+16 tests cachés à la soumission

Pour aller plus loin

Une phrase telle que Was it a car or a cat I saw est un palindrome si l’on ne tient pas compte de la casse, des espaces et de la ponctuation. Comment modifieriez-vous les deux pointeurs pour ignorer ces caractères ?

Indices

Ouvrez-les un par un. Chacun en dévoile un peu plus.

0 sur 3 ouverts

Solution

Un palindrome est égal à son inverse ; la vérification directe construit donc l’inverse et le compare. La meilleure vérification ne construit rien : le premier caractère doit correspondre au dernier, le deuxième à l’avant-dernier, et ainsi de suite jusqu’au milieu. Deux index qui avancent l’un vers l’autre vérifient ces paires sur place et s’arrêtent à la première différence.

Comparez la chaîne à son inverse

Intuition

Lire s de la même façon dans les deux sens signifie que s est égal à son inverse. Il suffit donc de l’inverser et de comparer : l’inverse de racecar est racecar, tandis que l’inverse de coddy est yddoc, qui est différent.

Construire l’inverse et le comparer nécessite de parcourir chaque caractère une seule fois, donc le temps d’exécution est O(n). La copie inversée contient n caractères supplémentaires, ce qui représente un espace supplémentaire de O(n) : pour n = 5 × 10^4, cela correspond à 50 000 caractères construits uniquement pour être comparés puis supprimés.

Cette méthode effectue également tout le travail à chaque fois. On peut déterminer que coddy ne convient pas en examinant ses première et dernière lettres, mais cette approche inverse les cinq caractères avant de les examiner.

Algorithme

Construis l’inverse de s, avec la fonction d’inversion du langage ou une boucle allant du dernier caractère au premier.
Compare l’inverse avec s.
Renvoie true s’ils sont égaux et false sinon.

def isPalindrome(s):
    return s == s[::-1]

Deux pointeurs depuis les deux extrémités

Intuition

L’inversion déplace le caractère à l’index i vers l’index n-1-i, donc s est égal à son inverse exactement lorsque s[i] est égal à s[n-1-i] pour chaque i. Chaque paire apparaît deux fois dans cette liste, donc vérifie seulement la moitié gauche. Place left à l’index 0 et right à l’index n-1, compare les deux caractères, puis déplace les deux pointeurs d’un pas vers l’intérieur.

Arrête-toi lorsque les pointeurs se rejoignent ou se croisent. Dans racecar, ils vérifient les paires d’index (0, 6), (1, 5) et (2, 4), puis se rejoignent à l’index 3, sur le e du milieu, qui n’a pas besoin de partenaire. Dans abba, ils vérifient (0, 3) et (1, 2), puis se croisent. La première paire différente prouve que la réponse est false, donc retourne immédiatement : le résultat pour coddy est déterminé après une seule comparaison.

Il y a au plus n / 2 comparaisons, ce qui correspond à un temps de O(n), et la seule mémoire utilisée est celle de deux index, soit un espace de O(1). R fait exception : il lit d’abord la chaîne sous forme de vecteur de codes de caractères, ce qui coûte O(n).

Algorithme

Définis left = 0 et right = n-1.
Tant que left < right, compare s[left] avec s[right].
S’ils sont différents, renvoie false.
Sinon, ajoute 1 à left, soustrais 1 à right et recommence.
Lorsque les pointeurs se rejoignent ou se croisent, chaque paire correspond : renvoie true.

def isPalindrome(s):
    left, right = 0, len(s) - 1
    while left < right:
        if s[left] != s[right]:
            return False
        left += 1
        right -= 1
    return True

Pièges et cas limites

La boucle est courte, donc les erreurs se trouvent dans ses limites et ses instructions de retour.

Renvoyer true dès qu’une paire correspond. abca passe sa paire extérieure et échoue sur la paire intérieure, donc true ne peut être renvoyé qu’après la fin de la boucle.
Initialiser right à n au lieu de n-1, ce qui entraîne une lecture au-delà de la fin (en C, le '\0' de terminaison). En Lua et en R, les index vont de 1 à n, donc dans ces langages, right commence à n.
Comparer des chaînes par leur adresse. En C, reversed == s compare deux pointeurs et renvoie toujours faux pour une copie fraîche ; utilisez strcmp.
Construire la chaîne inversée avec result = result + ch dans une boucle. À chaque étape, toute la chaîne déjà construite est copiée, soit environ 1.25 × 10^9 copies de caractères pour 50 000 lettres.
Indexer une chaîne Swift avec un entier. Cela ne compile pas ; parcourez s.utf8 avec ses propres index ou copiez les caractères dans un tableau.

Questions fréquentes4

Comment vérifier si une chaîne est un palindrome ?

Comparez le premier caractère avec le dernier, le deuxième avec l’avant-dernier, et ainsi de suite vers le milieu. Si une paire diffère, la chaîne n’est pas un palindrome ; si toutes les paires correspondent, elle en est un. Deux indices qui commencent aux deux extrémités et avancent vers l’intérieur permettent de faire cela en un seul parcours.

Peux-tu vérifier si une chaîne est un palindrome sans mémoire supplémentaire ?

Oui. La vérification avec deux pointeurs lit les caractères sur place et ne stocke que deux indices, elle utilise donc un espace supplémentaire de O(1). Comparer s à son inverse est plus court à écrire, mais crée une deuxième chaîne de n caractères.

Quelle est la complexité temporelle de la vérification d’une chaîne palindrome ?

C'est O(n) pour une chaîne de longueur n. La vérification à deux pointeurs effectue au plus n / 2 comparaisons et s'arrête à la première différence, donc une chaîne dont le premier et le dernier caractère diffèrent est déterminée après une seule comparaison.

Un caractère seul est-il un palindrome ?

Oui. Un caractère se lit de la même façon dans les deux sens, donc la réponse est true. Dans la boucle à deux pointeurs, left et right commencent tous deux à l’index 0, la boucle ne s’exécute jamais et la fonction renvoie true.

Python

def isPalindrome(s):
    # Écrivez le code ici

Cas de test

Cas 1

Cas 2

Cas 3

Entrée

s = "racecar"

Attendu

true