Palindrome et Python: comment reconnaître ?

Palindrome et Python font bon ménage. Dans cet article, nous allons manipuler les chaînes de caractères ainsi que les dictionnaires en Python. Nous allons voir plusieurs méthodes pour reconnaître une chaîne palindrome. Cela nous donnera l’occasion de manipuler les classes, les dictionnaires ainsi que certaines méthodes Python concernant les chaînes de caractères.

Avant de commencer cet article, n’oubliez pas que des ressources Python pour le lycée sont aussi disponibles sur ce site.

Au menu sur cette page...

Rappels sur les palindromes

Un palindrome est une entité qui se lit de la même façon de gauche à droite et de droite à gauche. Par exemple, « laval » est un mot palindrome. De même, » la mariée ira mal » est une phrase palindrome. Concernant les nombres, « 12321 » est aussi un palindrome.

Exploiter la symétrie d’un palindrome en Python

Un palindrome est symétrique : nous allons donc exploiter celle-ci avec Python pour voir si une chaîne de caractères est un palindrome.

Étant donnée une chaîne de caractère « a », on s’appuie sur le fait que a[0] représente le premier caractère de « a » et que a[-1] représente son dernier caractère. Nous construisons donc une fonction qui va admettre pour argument une chaîne de caractères « a » et qui teste l’égalité du 1er et dernier caractère, puis du 2ème et pénultième caractère, puis du 3ème et antépénultième caractères, etc.

def is_palindrome(a):
    for i in range(len(a)//2):
        if a[i] != a[-i-1]:
            return False
    return True

Dans cette fonction,

on parcourt la moitié de la chaîne de caractères « a ». Ici, « len(a) désigne la longueur de la chaîne, et len(a)//2 représente le quotient de la division euclidienne de cette longueur par 2. Ainsi, si « a » a une longueur impaire, on s’arrête au caractère juste avant celui du milieu;
dans la boucle for, on teste si le caractère de rang i est différent du caractère de rang –i-1. Il faut ici faire attention au fait que, par exemple, a[0] représente le 1er caractère alors que a[-1] représente le dernier, d’où le décalage : on ne marque pas a[-i] mais a[-i-1]. Si les caractères sont différents alors la chaîne n’est pas un palindrome. On retourne donc False, ce qui stoppe la boucle;
on finit par retourner True si False n’a pas été retourné.

Standardiser la chaîne de caractères pour reconnaître un palindrome en Python

La phrase : « Tu l’as trop écrasé, César, ce Port-Salut » est un palindrome. Mais en l’état, la fonction précédemment écrit ne la reconnaît pas comme un palindrome : il est nécessaire de standardiser l’écriture de la chaîne, c’est-à-dire de tout mettre en minuscules, de remplacer les caractères accentués par leur équivalent sans accents et d’enlever les caractères « gênants » comme les espaces et les signes de ponctuation. On va donc faire appel à un dictionnaire car (comme « caractères ») :

car = {
        "à" : "a",
        "ä" : "a",
        "â" : "a",
        "ç" : "c",
        "é" : "e",
        "è" : "e",
        "ë" : "e",
        "ï" : "i",
        "ô" : "o",
        "ù" : "u",
        "ü" : "u",
        "û" : "u",
        " " : "",
        "-" : "",
        "," : "",
        "'" : "",
        "?" : "",
        "!" : "",
        "." : ""
    }

Les clés de ce dictionnaire sont les caractères à remplacer et leur valeur sont les caractères à substituer. Par exemple, l’espace est remplacé par un vide (comme tous les caractères de ponctuation).

Il ne reste plus qu’à écrire une fonction qui se charge de tout mettre en minuscules puis d’effectuer les substitutions :

def moulinette(a):
    a = a.lower()
    for cle,valeur in car.items():
        a = a.replace(cle,valeur)
    return a

On lance le tout

a = moulinette(input("Entrez une phrase : "))

if is_palindrome(a) == True:
    print("C'est un palindrome.")
else:
    print("Ce n'est pas un palindrome.")

Ici, je passe tout de suite à la moulinette ce que je rentre au clavier, puis je teste si c’est un palindrome.

Le programme complet

# Reconnaître si une chaîne de caractères est palindrome

def is_palindrome(a):
    for i in range(len(a)//2):
        if a[i] != a[-i-1]:
            return False
    return True

# Dictionnaire associatif des caractères accentuées en langue francophone

car = {
        "à" : "a",
        "ä" : "a",
        "â" : "a",
        "ç" : "c",
        "é" : "e",
        "è" : "e",
        "ë" : "e",
        "ï" : "i",
        "ô" : "o",
        "ù" : "u",
        "ü" : "u",
        "û" : "u",
        " " : "",
        "-" : "",
        "," : "",
        "'" : "",
        "?" : "",
        "!" : "",
        "." : ""
    }

# Remplacer des caractères par d'autres

def moulinette(a):
    a = a.lower()
    for cle,valeur in car.items():
        a = a.replace(cle,valeur)
    return a

# MAIN

a = moulinette(input("Entrez une phrase : "))

if is_palindrome(a) == True:
    print("C'est un palindrome.")
else:
    print("Ce n'est pas un palindrome.")

La version « class »

Une autre manière de coder ceci est de passer par une classe. Bon, ici, ce n’est pas vraiment utile (pour ce genre d’exercice…) mais cela me donne l’occasion d’en parler…

L’idée est donc ici de créer une classe palindrome qui peut retourner:

soit la chaîne de caractères une fois passée à la moulinette;
soit la réponse (à savoir si c’est un palindrome ou non).

Voyons de suite le code complet:

car = {
        "à" : "a",
        "ä" : "a",
        "â" : "a",
        "ç" : "c",
        "é" : "e",
        "è" : "e",
        "ë" : "e",
        "ï" : "i",
        "ô" : "o",
        "ù" : "u",
        "ü" : "u",
        "û" : "u",
        " " : "",
        "-" : "",
        "," : "",
        "'" : "",
        "?" : "",
        "!" : "",
        "." : ""
    }


class palindrome:
    def __init__(self,chain):
        self.chain = chain

    def moulinette(self):
        a = self.chain.lower()
        for cle,valeur in car.items():
            a = a.replace(cle,valeur)
        return str(a)

    def is_it(self):
        pal = True
        a = palindrome(self.chain).moulinette()

        for i in range(len(a)//2):
            if a[i] != a[-i-1]:
                pal = False
                break

        if pal == True:
            print("C'est un palindrome !")
        else:
            print("Ce n'est pas un palindrome...")

palindrome(input("Entrez une chaîne de caractères : ")).is_it()

La première partie de la classe permet de faire en sorte que la classe palindrome admette un argument;
ensuite, on créé des méthodes liées à la classe : moulinette et is_it.

Une méthode plus rapide pour reconnaître un palindrome en Python

Cette méthode est intéressante car très courte.

Il suffit en effet d’utiliser la librairie unidecode (pour transformer les caractères accentués en leur équivalents sans accent), la méthode [::-1] (appliquée à une chaîne de caractères) pour la renverser et la méthode lower().

Cela donne alors:

from unidecode import unidecode

phrase = input('Entrez une phrase, un mot ou un nombre : ')
symb = [ "'" , ":" , ";" , "," , "-" , "?" , "!" , " " , "." ]
for i in phrase:
    if i in symb:
        phrase = phrase.replace(i,"")

if unidecode(phrase.lower()) == unidecode(phrase[::-1].lower()):
    print("C'est un palindrome !")
else:
    print("Ce n'est pas un palindrome...")

Avouez que c’est bien plus rapide !

Ici, après avoir saisi la phrase (ou le mot), on commence par exclure les symboles qui sont dans la liste symb (lignes 4 à 7), puis on compare la phrase ainsi obtenue (en minuscules et sans accent) à son inverse.

En une ligne…

Il est aussi possible de faire bien plus rapide à l’aide d’une fonction lambda (par exemple):

is_palindrome = lambda n: str(n) == str(n)[::-1] if isinstance(n,int) else n == n[::-1] if isinstance(n,str) else False

>>> is_palindrome(12345)
False
>>> is_palindrome(1234554321)
True
>>> is_palindrome('abccba')
True

Ça, c’est vraiment la classe… 🙂

Bien sûr, avec cette version, il faut faire attention aux caractères accentués. Si on ajoute à cela les majuscules, on n’est pas sortir de l’affaire! Allez, on y va, mais la promesse d’une ligne n’est plus tenue car on fait tout de même appel à la libraire unidecode.

from unidecode import unidecode

is_palindrome = lambda n: str(n) == str(n)[::-1] if isinstance(n,int) else unidecode(n).replace(' ','').lower() == unidecode(n)[::-1].replace(' ','').lower() if isinstance(n,str) else False

>>> is_palindrome('Noël a trop par rapport à Léon')
True

Il ne reste plus que les autres sigles (signes de ponctuation) à éliminer.

from unidecode import unidecode

epure = lambda c: ''.join( [ i for i in c if i not in [ "'" , ":" , ";" , "," , "-" , "?" , "!" , " " , "." ] ] )

is_palindrome = lambda n: str(n) == str(n)[::-1] if isinstance(n,int) else epure(unidecode(n)).replace(' ','').lower() == epure(unidecode(n))[::-1].replace(' ','').lower() if isinstance(n,str) else False

>>> is_palindrome('Noël a trop par rapport à Léon.')
True

Ça fait le job! Cela dit, c’est assez peu lisible hein ?

Palindrome en Python: comment savoir si une chaîne de caractères en est?