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 en allant vers le milieu. Si une paire diffère, la chaîne n’est pas un palindrome. Deux index qui commencent aux deux extrémités et se déplacent vers l’intérieur permettent de le faire en un seul passage.

Q: Peux-tu vérifier si un mot est un palindrome sans mémoire supplémentaire ?

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

Q: Quelle est la complexité temporelle pour vérifier si une chaîne est un palindrome ?

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 coddy nécessite une seule comparaison.

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

Oui, la lecture est la même dans les deux sens. 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 que 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 manière 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.

Pour aller plus loin

Comment modifierais-tu les deux pointeurs pour ignorer les espaces et la ponctuation, et ne pas tenir compte de la casse, afin que Was it a car or a cat I saw soit considéré comme un palindrome ?

Indices

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

0 sur 3 ouverts

Solution

Un palindrome est égal à son propre inverse : tu peux donc construire l’inverse et le comparer. Tu n’as pas besoin de la copie : le premier caractère doit correspondre au dernier, le deuxième à l’avant-dernier, et ainsi de suite. Deux index qui avancent vers le centre vérifient ces paires sur place et s’arrêtent à la première différence.

Comparez la chaîne à son inverse

Intuition

Inverse s et compare : racecar inversé donne racecar, et coddy inversé donne yddoc. Une chaîne se lit exactement de la même façon dans les deux sens lorsqu’elle est égale à son inverse.

Le temps d’exécution est de O(n), mais la copie inversée occupe un espace supplémentaire de O(n), soit 50 000 caractères pour n = 5 × 10^4. Le travail est aussi toujours complet : on peut déterminer le résultat pour coddy à partir de sa première et de sa dernière lettre, mais les cinq lettres sont d’abord inversées.

Algorithme

Construis l'inverse de s, à l'aide de la fonction d'inversion du langage ou d'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

Inverser déplace 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 tout i. Chaque paire apparaît deux fois dans cette condition, donc vérifier la moitié gauche suffit. Dans racecar, les paires sont (0, 6), (1, 5) et (2, 4) ; le e du milieu à l’index 3 n’a pas besoin de partenaire.

La première paire qui diffère prouve que la réponse est false, donc le cas de coddy est résolu après une comparaison. Au plus n / 2 comparaisons sont effectuées, soit un temps en O(n), et deux index occupent un espace en O(1). R lit d’abord la chaîne sous forme de vecteur de codes de caractères, ce qui coûte O(n).

Algorithme

Définissez left = 0 et right = n-1.
Tant que left < right, comparez s[left] avec s[right].
S’ils sont différents, renvoyez false.
Sinon, ajoutez 1 à left, soustrayez 1 de right et recommencez.
Lorsque les pointeurs se rejoignent ou se croisent, chaque paire correspond : renvoyez 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

Renvoyer true dès qu’une paire correspond. abca valide sa paire extérieure et échoue sur la paire intérieure ; true n’est donc renvoyé qu’après la boucle.
Initialiser right à n au lieu de n-1, ce qui lit au-delà de la fin (en C, le '\0' de terminaison). En Lua et en R, les index vont de 1 à n ; right commence donc bien à n.
Comparer des chaînes avec == en C. reversed == s compare deux pointeurs et renvoie false pour une copie ; utilise strcmp.
Construire la chaîne inversée avec result = result + ch. À chaque étape, la chaîne obtenue jusque-là est copiée : environ 1.25 × 10^9 copies de caractères pour 50,000 lettres.
Indexer une chaîne Swift avec un entier : le code ne compile pas. Parcours s.utf8 ou copie 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 en allant vers le milieu. Si une paire diffère, la chaîne n’est pas un palindrome. Deux index qui commencent aux deux extrémités et se déplacent vers l’intérieur permettent de le faire en un seul passage.

Peux-tu vérifier si un mot est un palindrome sans mémoire supplémentaire ?

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

Quelle est la complexité temporelle pour vérifier si une chaîne est un palindrome ?

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 coddy nécessite une seule comparaison.

Un seul caractère est-il un palindrome ?

Oui, la lecture est la même dans les deux sens. 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.

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

Test #1

Test #2

Test #3

Argument

s = "racecar"

Résultat attendu

true