Vérifiez si deux chaînes sont des anagrammes à l'aide de Python

1. Vérifiez si deux chaînes sont des anagrammes à l’aide du tri en Python
2. Vérifiez si deux chaînes sont des anagrammes à l’aide de dictionnaires de fréquence en Python

Une anagramme est un mot formé en réarrangeant les lettres d’un autre mot.

Par exemple, race et care, listen et silent, fried et fired, knee et keen sont des paires d’anagrammes. dad et bad, apple et mango, hello et world ne sont pas des anagrammes.

En utilisant des langages de programmation, nous pouvons vérifier rapidement si deux chaînes sont des anagrammes l’une de l’autre ou non.

Cet article montrera comment vérifier si deux chaînes sont des anagrammes ou n’utilisent pas Python. Nous allons parler de quelques approches pour le même.

Vérifiez si deux chaînes sont des anagrammes à l’aide du tri en Python

Pour vérifier si deux chaînes sont des anagrammes ou non, nous pouvons trier les deux chaînes et vérifier si elles sont égales ou non. Reportez-vous au code suivant pour la même chose.

La complexité temporelle du code est O(nlogn) à cause du tri, et la complexité spatiale est O(1), car nous ne stockons aucune valeur.

def check_anagram(a, b):
    if a is None or b is None or len(a) != len(b):
        return "Not Anagram"

    return "Anagram" if sorted(a) == sorted(b) else "Not Anagram"


print(check_anagram("keen", "knee"))
print(check_anagram("race", "care"))
print(check_anagram("fried", "fired"))
print(check_anagram("apple", "paddle"))
print(check_anagram("first", "second"))
print(check_anagram(None, "second"))
print(check_anagram("first", None))
print(check_anagram(None, None))

Production :

Anagram
Anagram
Anagram
Not Anagram
Not Anagram
Not Anagram
Not Anagram
Not Anagram

Vérifiez si deux chaînes sont des anagrammes à l’aide de dictionnaires de fréquence en Python

Pour vérifier si deux chaînes sont des anagrammes, nous pouvons conserver le nombre de caractères présents dans les deux chaînes et comparer les nombres. Si elles étaient identiques, cela signifie que les deux chaînes sont des anagrammes. Sinon, ils ne le sont pas.

Reportez-vous au code suivant pour la même chose.

La complexité temporelle de la solution suivante est O(n) puisque nous itérons sur les deux chaînes. La complexité temporelle moyenne d’ajout d’un élément au dictionnaire et de récupération d’un élément est O(1).

De plus, comparer deux dictionnaires avec le même nombre de clés est O(n). Et, la complexité spatiale est O(n) parce que nous maintenons deux dictionnaires, et en coulisse, les dictionnaires utilisent des tableaux pour stocker les clés et les valeurs.

def check_anagram(a, b):
    if a is None or b is None or len(a) != len(b):
        return "Not Anagram"

    counts_a = {}
    counts_b = {}

    for x in a:
        if x not in counts_a.keys():
            counts_a[x] = 1
        else:
            counts_a[x] += 1

    for x in b:
        if x not in counts_b.keys():
            counts_b[x] = 1
        else:
            counts_b[x] += 1

    return "Anagram" if counts_a == counts_b else "Not Anagram"


print(check_anagram("keen", "knee"))
print(check_anagram("race", "care"))
print(check_anagram("fried", "fired"))
print(check_anagram("apple", "paddle"))
print(check_anagram("first", "second"))
print(check_anagram(None, "second"))
print(check_anagram("first", None))
print(check_anagram(None, None))

Production :

Anagram
Anagram
Anagram
Not Anagram
Not Anagram
Not Anagram
Not Anagram
Not Anagram