Valid Palindrome

Q: Quelle est la complexité temporelle de Valid Palindrome ?

Les deux approches s’exécutent en temps O(n) , car chaque caractère est examiné un nombre constant de fois. Le nettoyage préalable nécessite O(n) de mémoire supplémentaire pour la copie. La version à deux pointeurs utilise O(1) de mémoire supplémentaire, puisqu’elle ne conserve que deux index.

Q: Comment vérifier si une chaîne est un palindrome en ignorant les caractères non alphanumériques ?

Gardez un pointeur à chaque extrémité de la chaîne. Déplacez un pointeur au-delà de tout caractère qui n’est ni une lettre ni un chiffre et, lorsque les deux pointeurs se trouvent sur des lettres ou des chiffres, comparez-les en minuscules. Si toutes les paires comparées correspondent jusqu’à ce que les pointeurs se rejoignent, la chaîne est un palindrome.

Q: Une chaîne vide est-elle un palindrome ?

Oui. Un texte vide se lit de la même façon dans les deux sens, donc une chaîne telle que ?!-_ , dont tous les caractères sont ignorés, renvoie true . Les deux approches obtiennent ce résultat sans code supplémentaire : le texte nettoyé est égal à son inverse vide, et les deux pointeurs ne trouvent jamais de paire différente.

Q: Pourquoi utiliser deux pointeurs au lieu d’inverser la chaîne ?

L’inversion nécessite une copie nettoyée et une copie inversée, ce qui représente une mémoire supplémentaire de O(n) . Deux pointeurs comparent les mêmes paires sur place et peuvent s’arrêter à la première différence, souvent après quelques étapes. Les intervieweurs demandent généralement cette version en question complémentaire.

FacileDeux pointeurs

+10

Tu reçois une chaîne de caractères s. Ne garde que ses lettres et ses chiffres, considère les majuscules et les minuscules comme la même lettre, et détermine si le résultat se lit de la même façon de gauche à droite et de droite à gauche. Retourne true si c’est le cas et false sinon.

Tous les autres caractères, tels que ., !, ?, :, ;, - ou _, sont ignorés. Si s ne contient aucune lettre ni aucun chiffre, il ne reste rien, et un texte vide est considéré comme un palindrome.

Fonction

isPalindrome(s: string) → boolean

sstring: le texte à vérifier, ponctuation comprise
Renvoieboolean: vrai si les lettres et les chiffres de s se lisent de la même façon dans les deux sens, sans tenir compte de la casse

Contraintes

1 ≤ s.length ≤ 5 × 10⁴
s contient des lettres anglaises, des chiffres et les signes de ponctuation . ! ? : ; - _, sans espaces.

Exemples

Entrée: s = "Was_it_a_car_or_a_cat_I_saw?"
Sortie: true
Explication: Supprimez les traits de soulignement et le point d’interrogation, puis mettez les majuscules en minuscules : vous obtenez wasitacaroracatisaw, qui est identique à l’envers.

Entrée: s = "race-a-car"
Sortie: false
Explication: Sans les traits d’union, le texte est raceacar. En le lisant de droite à gauche, il commence par raca au lieu de race : le e au milieu a un a comme partenaire miroir, donc la réponse est false.

Entrée: s = "Step-on-no-pets!"
Sortie: true
Explication: Le texte conservé est steponnopets. Le S majuscule correspond au s final, car la casse est ignorée, et les traits d’union ainsi que le ! ne jouent aucun rôle.

+25 tests cachés à la soumission

Pour aller plus loin

Peux-tu déterminer cela avec une mémoire supplémentaire de O(1), sans créer de copie nettoyée de s ?

Indices

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

0 sur 3 ouverts

Solution

La vérification du palindrome elle-même est classique : le premier caractère conservé doit être égal au dernier, le deuxième doit être égal à l’avant-dernier, et ainsi de suite. Ce qui rend cette version délicate, c’est que les caractères que vous comparez ne se trouvent pas à des indices symétriques dans s, car la ponctuation est répartie de manière inégale des deux côtés. Vous pouvez la supprimer au préalable, ou laisser deux pointeurs l’ignorer en avançant l’un vers l’autre.

Nettoie la chaîne, puis compare-la à sa version inversée

Intuition

Construis le texte dont parle réellement le problème. Parcours s, garde chaque lettre ou chiffre en minuscule et ignore tout le reste. Pour Step-on-no-pets!, on obtient steponnopets. La question est maintenant la question habituelle du palindrome : ce texte est-il égal à son propre inverse ?

C’est correct, car le nettoyage supprime exactement les caractères que le problème demande d’ignorer et uniformise la casse qu’il demande d’ignorer. Si s ne contient aucune lettre ni aucun chiffre, le texte nettoyé est vide, et un texte vide est égal à son inverse : la réponse est donc true, sans cas particulier.

Chaque caractère est lu une fois pour le nettoyage, puis une fois de plus pour la comparaison : le temps d’exécution est donc de O(n). La copie nettoyée et son inverse nécessitent O(n) de mémoire supplémentaire, ce que l’approche suivante permet d’éviter.

Algorithme

Crée un texte vide cleaned.
Pour chaque caractère de s, s'il s'agit d'une lettre ou d'un chiffre, ajoute-le en minuscules.
Inverse cleaned.
Retourne si cleaned est égal à son inverse.

def isPalindrome(s):
    cleaned = [ch.lower() for ch in s if ch.isalnum()]
    return cleaned == cleaned[::-1]

Deux pointeurs qui ignorent la ponctuation

Intuition

La copie nettoyée sert uniquement à comparer les caractères en miroir. Tu peux faire la même comparaison directement sur s. Place left sur le premier indice et right sur le dernier. À chaque étape, si left pointe vers un signe de ponctuation, avance-le vers la droite ; si right pointe vers un signe de ponctuation, recule-le vers la gauche. Une fois que les deux pointent vers des lettres ou des chiffres, compare-les en minuscules. Une différence signifie false ; une correspondance signifie que les deux pointeurs avancent vers le centre.

Pourquoi s’agit-il de la même vérification ? Les pointeurs s’arrêtent toujours sur le prochain caractère conservé à partir de chaque extrémité. Ils parcourent donc les paires (premier caractère conservé, dernier caractère conservé), (deuxième caractère conservé, avant-dernier caractère conservé), et ainsi de suite, qui sont exactement les paires examinées par la comparaison avec la chaîne inversée. Dans Abc-dcbX, la première paire est A et X, et la réponse est false après une seule comparaison.

À chaque étape, au moins un pointeur avance, et ils s’arrêtent lorsqu’ils se rejoignent ; la boucle s’exécute donc au plus n fois. À part les deux indices, rien n’est stocké, ce qui donne une mémoire supplémentaire de O(1).

Algorithme

Définissez left = 0 et right = n-1.
Tant que left < right : si s[left] n’est pas une lettre ou un chiffre, augmentez left et continuez.
Sinon, si s[right] n’est pas une lettre ou un chiffre, diminuez right et continuez.
Sinon, comparez les deux caractères en minuscules. S’ils sont différents, renvoyez false ; s’ils correspondent, déplacez les deux pointeurs vers l’intérieur.
Lorsque les pointeurs se rejoignent, renvoyez true.

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

Pièges et cas limites

La plupart des bogues proviennent des caractères ignorés et de la casse.

Comparer s[i] à s[n-1-i] dans la chaîne brute. a-ba est un palindrome une fois le trait d’union supprimé, mais le miroir brut du - à l’index 1 est le b à l’index 2.
Déplacer les deux pointeurs lorsqu’un seul d’entre eux se trouve sur un signe de ponctuation. Ignore un côté à la fois, sinon les deux côtés se décalent.
Ignorer les signes de ponctuation dans une boucle interne qui dépasse l’autre pointeur. Avec ?!-_, une boucle interne sans limite dépasse la fin de la chaîne ; vérifie left < right à chaque déplacement.
Traiter les chiffres comme du bruit. 0P vaut false : le chiffre 0 est conservé et comparé, et ce n’est pas la lettre p.
Renvoyer false lorsque rien n’est conservé. Une chaîne composée uniquement de signes de ponctuation, comme ., a un texte nettoyé vide, qui est un palindrome.
Une chaîne composée uniquement de chiffres, comme 12321, peut être interprétée comme un nombre par PHP et R. Convertis-la d’abord en chaîne.

Questions fréquentes4

Quelle est la complexité temporelle de Valid Palindrome ?

Les deux approches s’exécutent en temps O(n), car chaque caractère est examiné un nombre constant de fois. Le nettoyage préalable nécessite O(n) de mémoire supplémentaire pour la copie. La version à deux pointeurs utilise O(1) de mémoire supplémentaire, puisqu’elle ne conserve que deux index.

Comment vérifier si une chaîne est un palindrome en ignorant les caractères non alphanumériques ?

Gardez un pointeur à chaque extrémité de la chaîne. Déplacez un pointeur au-delà de tout caractère qui n’est ni une lettre ni un chiffre et, lorsque les deux pointeurs se trouvent sur des lettres ou des chiffres, comparez-les en minuscules. Si toutes les paires comparées correspondent jusqu’à ce que les pointeurs se rejoignent, la chaîne est un palindrome.

Une chaîne vide est-elle un palindrome ?

Oui. Un texte vide se lit de la même façon dans les deux sens, donc une chaîne telle que ?!-_, dont tous les caractères sont ignorés, renvoie true. Les deux approches obtiennent ce résultat sans code supplémentaire : le texte nettoyé est égal à son inverse vide, et les deux pointeurs ne trouvent jamais de paire différente.

Pourquoi utiliser deux pointeurs au lieu d’inverser la chaîne ?

L’inversion nécessite une copie nettoyée et une copie inversée, ce qui représente une mémoire supplémentaire de O(n). Deux pointeurs comparent les mêmes paires sur place et peuvent s’arrêter à la première différence, souvent après quelques étapes. Les intervieweurs demandent généralement cette version en question complémentaire.

Python

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

Cas de test

Cas 1

Cas 2

Cas 3

Entrée

s = "Was_it_a_car_or_a_cat_I_saw?"

Attendu

true