Valid Palindrome

Description

[EN]

Given a string s, return true if it is a palindrome, otherwise return false.

A palindrome is a string that reads the same forward and backward. It is also case-insensitive and ignores all non-alphanumeric characters.

[FR]

Étant donné une chaîne de caractères s, retournez true si elle est un palindrome, sinon retournez false.

Un palindrome est une chaîne qui se lit de la même façon de gauche à droite et de droite à gauche. Le test de palindrome est insensible à la casse (les majuscules et minuscules sont considérées comme identiques) et ignore tous les caractères non alphanumériques (comme les espaces, la ponctuation, etc.).

Approche: Utilisation d'un double pointeur

Pour résoudre ce problème, je suis passé par l'utilisation d'un double pointeur

• Logique : on enlève d'abord tous les caractères non alphanumériques de la chaîne de caractères, et on met tous les caractères en minuscule. Ensuite, en utilisant deux pointeurs, on fait un parcours de la chaîne de caractère depuis la droite et un autre depuis la gauche en utilisant deux pointeurs. A chaque itération, on vérifie si les deux caractères actuellement pointés sont identiques. Dès que l'on tombe sur une différence, alors la chaîne n'est pas un palindrome. Si par contre on réussit à effectuer le parcours, on peut renvoyer true à la fin de la boucle.

• Complexité temporelle : Avec une boucle,la complexité temporelle est de O(n)

• Complexité spatiale : l'utilisation d'un tableau nécessite un espace supplémentaire et donc la complexité spatiale est de O(n)