Reconnaître une chaîne de caractères palindrome avec Python

Reconnaître une chaîne de caractères palindrome avec Python

Dans cet article, nous allons manipuler les chaînes de caractères ainsi que les dictionnaires en Python.

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

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.

Etant 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

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 dictionnaires 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.

Stéphane Pasquet
Stéphane Pasquet

Laissez votre message