Anagrammes et Python

Anagrammes et Python

Comment vérifier que deux chaînes de caractères sont des anagrammes en Python ? Plusieurs logiques peuvent être envisagées. Regardons cela.

anagrammes en Python

Qu’est-ce qu’une anagramme ?

ben oui, avant de parler d’anagrammes, il faut savoir ce que c’est non ?

Une anagramme (oui, c’est féminin) d’une chaîne de caractères est une chaîne de caractères formée des mêmes caractères mis dans un ordre différent.

Ainsi, “ABC” et “BAC” sont deux anagrammes.

Nous allons supposer par la suite que a et b sont deux chaînes de caractères de même longueur (pour les calculs de complexité).

Anagrammes et Python : première méthode

La méthode la plus simple pour voir si deux chaînes de caractères sont anagrammes est la suivante:

def anagramme(a,b):
    if sorted(a) == sorted(b):
        return True
    else:
        return False

La complexité est en \(\mathcal{O}(n\ln n)\) en moyenne, où n est le nombre de caractères d’une chaîne. En effet, l’algorithme de tri utilisé par Python est timsort.

Une deuxième approche : anagrammes et Python

Cette méthode est quasi-analogue à la précédente, si ce n’est qu’elle fait appel au module collections.

from collections import Counter

def anagramme(a,b):
    if Counter(a) == Counter(b):
        return True
    else:
        return False

Counter(a) est un objet, défini par la classe Counter, qui se comporte comme un dictionnaire. C’est d’ailleurs une sous-classe de dict.

La complexité de cette solution est alors en \(\mathcal{O}(n)\).

Une troisième approche : anagrammes et Python

S’inspirant de la méthode précédente, on peut construire directement un dictionnaire à partir de la chaîne de caractères:

def anagramme(a,b):
    dict_a , dict_b = dict() , dict()
    for i in a:
        dict_a[i] = 1 if i not in dict_a else dict_a[i]+1
    for i in b:
        dict_b[i] = 1 if i not in dict_b else dict_b[i]+1
    
    if dict_a == dict_b:
        return True
    else:
        return False

On voit bien ici que la complexité est en \(\mathcal{O}(n)\).

Conclusion

Si on cherche a avoir une complexité minimale, ainsi qu’une syntaxe minimale, il vaut mieux utiliser le module collections et la classe Counter.

Cet article est en marge des ressources Python pour le lycée, disponibles sur cette page.

Stéphane Pasquet
Stéphane Pasquet

Laissez votre message