Valid Anagram

Q: Quelle est la complexité temporelle de Valid Anagram ?

Le comptage des lettres prend un temps O(n) et un espace supplémentaire O(1) , car le tableau de compteurs comporte 26 entrées quelle que soit la longueur des chaînes. Le tri des deux chaînes prend un temps O(n log n) et généralement un espace O(n) pour les copies triées.

Q: Est-il préférable de trier ou de compter pour vérifier s’il s’agit d’une anagramme ?

Le comptage est plus rapide en théorie, O(n) contre O(n log n) , et il peut s’arrêter dès qu’une lettre est utilisée trop souvent. Le tri est plus court à écrire et fonctionne pour n’importe quel alphabet sans modification. Lors d’un entretien, présente d’abord le tri, puis améliore-le en utilisant le comptage.

FacileHachage Tri

+10

Deux chaînes sont des anagrammes lorsque l’une est une réorganisation de l’autre : elles utilisent les mêmes lettres, et chaque lettre apparaît le même nombre de fois. On vous donne deux chaînes s et t composées de lettres minuscules de l’alphabet anglais. Renvoyez true si t est un anagramme de s, et false sinon.

Fonction

isAnagram(s: string, t: string) → boolean

sstring: la première chaîne, lettres minuscules
tstring: la chaîne à tester par rapport à s
Renvoieboolean: vrai si t utilise exactement les lettres de s, chacune le même nombre de fois

Contraintes

1 ≤ s.length, t.length ≤ 2 × 10⁴
s et t ne contiennent que des lettres minuscules anglaises (a à z).
Les deux longueurs peuvent différer.

Exemples

Entrée: s = "listen"t = "silent"
Sortie: true
Explication: Les deux mots contiennent chacun un e, un i, un l, un n, un s et un t, donc silent est listen avec ses lettres réarrangées.

Entrée: s = "aabb"t = "abbb"
Sortie: false
Explication: Les longueurs sont identiques et les deux utilisent uniquement a et b, mais aabb contient deux a et abbb en contient un. Le nombre d’occurrences doit correspondre, pas seulement les lettres.

Entrée: s = "cat"t = "cast"
Sortie: false
Explication: cast comporte quatre lettres et cat en comporte trois, donc aucune permutation de cat ne peut l’écrire.

+19 tests cachés à la soumission

Pour aller plus loin

Et si les chaînes pouvaient contenir n’importe quel caractère Unicode au lieu de a à z ? Comment modifierais-tu le comptage ?

Indices

Ouvrez-les un par un. Chacun en dévoile un peu plus.

0 sur 3 ouverts

Solution

Une anagramme conserve le nombre d’occurrences de chaque lettre et ignore leur ordre. Tu as donc besoin d’un résumé de chaque chaîne qui oublie où se trouvaient les lettres, mais retient combien il y en a de chaque. Le tri construit ce résumé en O(n log n) ; un tableau de 26 compteurs le construit en un seul parcours.

Trier les deux chaînes

Intuition

Le tri place les lettres d’une chaîne par ordre alphabétique et efface la position de départ de chacune. listen donne eilnst après le tri, tout comme silent : ce sont donc des anagrammes. aabb reste aabb et abbb reste abbb ; ils diffèrent à l’indice 1, ce ne sont donc pas des anagrammes.

Le test fonctionne dans les deux sens. Si t est une réorganisation de s, les deux chaînes contiennent les mêmes lettres le même nombre de fois, donc le tri produit la même séquence. Si les séquences triées sont égales, t utilise exactement les lettres de s.

Compare d’abord les longueurs : des chaînes de longueurs différentes ne sont jamais des anagrammes, et tu évites les deux tris. Le tri coûte O(n log n) en temps, et la plupart des langages trient une copie des caractères, ce qui nécessite O(n) d’espace supplémentaire. Pour n = 2 × 10^4, c’est rapide, mais l’approche par comptage nécessite moins de travail.

Algorithme

Si les longueurs de s et de t diffèrent, renvoie false.
Copie les caractères de chaque chaîne dans un tableau.
Trie les deux tableaux.
Renvoie true si les tableaux triés sont égaux, élément par élément.

def isAnagram(s, t):
    if len(s) != len(t):
        return False
    return sorted(s) == sorted(t)

Compter chaque lettre

Intuition

Seules 26 lettres peuvent apparaître ; garde donc un compteur par lettre dans un tableau de 26 éléments, avec l’indice 0 pour a et l’indice 25 pour z. L’indice d’une lettre correspond à son code de caractère moins le code de a. Parcours s et ajoute 1 au compteur de chaque lettre, puis parcours t et soustrais 1.

Tu peux t’arrêter plus tôt : un compteur inférieur à 0 signifie que t a utilisé cette lettre plus souvent que s. Pour aabb et abbb, après avoir parcouru s, les compteurs indiquent a : 2 et b : 2. Ensuite, t prend b trois fois ; la troisième fois, le compteur de b passe à -1, et tu renvoies false immédiatement.

Pourquoi « aucun compteur n’est passé sous zéro » suffit-il ? Les longueurs sont égales, donc la somme des compteurs est égale à 0 après les deux parcours. Si aucun n’est négatif, un compteur positif n’aurait rien pour le compenser : tous les compteurs sont donc égaux à 0 et les occurrences correspondent. C’est pourquoi la vérification de la longueur est nécessaire, et pas seulement un raccourci.

Chaque chaîne est parcourue une fois, ce qui prend un temps de O(n). Le tableau contient toujours 26 nombres, quelle que soit la longueur ; l’espace supplémentaire est donc de O(1).

Algorithme

Si les longueurs de s et t diffèrent, renvoie false.
Crée un tableau de 26 zéros.
Pour chaque lettre de s, ajoute 1 à son compteur.
Pour chaque lettre de t, soustrais 1 à son compteur ; s’il passe sous 0, renvoie false.
Renvoie true.

def isAnagram(s, t):
    if len(s) != len(t):
        return False
    counts = [0] * 26  # counts[0] is 'a', counts[25] is 'z'
    for ch in s:
        counts[ord(ch) - ord("a")] += 1
    for ch in t:
        index = ord(ch) - ord("a")
        counts[index] -= 1
        if counts[index] < 0:
            return False  # t uses this letter more often than s
    return True

Pièges et cas limites

La plupart des mauvaises réponses viennent du fait qu’on vérifie quelles lettres apparaissent au lieu de compter combien de fois elles apparaissent, ou qu’on omet la vérification de la longueur.

Comparer les ensembles de lettres. aabb et abbb utilisent exactement a et b, pourtant ce ne sont pas des anagrammes.
Vérifier que chaque lettre de t apparaît quelque part dans s sans la barrer. aab et abb réussissent ce test dans les deux sens.
Omettre la vérification de la longueur dans la version avec comptage. Avec s = ab et t = a, aucun compteur ne descend en dessous de 0, donc le code renverrait à tort true.
Indexer le tableau de compteurs avec le code brut du caractère. a vaut 97, bien au-delà de la fin d’un tableau de 26 éléments ; soustrayez d’abord le code de a. En Lua et en R, ajoutez 1, puisque leurs tableaux commencent à l’indice 1.

Questions fréquentes4

Quelle est la complexité temporelle de Valid Anagram ?

Le comptage des lettres prend un temps O(n) et un espace supplémentaire O(1), car le tableau de compteurs comporte 26 entrées quelle que soit la longueur des chaînes. Le tri des deux chaînes prend un temps O(n log n) et généralement un espace O(n) pour les copies triées.

Est-il préférable de trier ou de compter pour vérifier s’il s’agit d’une anagramme ?

Le comptage est plus rapide en théorie, O(n) contre O(n log n), et il peut s’arrêter dès qu’une lettre est utilisée trop souvent. Le tri est plus court à écrire et fonctionne pour n’importe quel alphabet sans modification. Lors d’un entretien, présente d’abord le tri, puis améliore-le en utilisant le comptage.

Comment vérifier les anagrammes qui contiennent des caractères Unicode ?

Remplace le tableau de 26 compteurs par une table de hachage associant chaque caractère à son nombre d’occurrences. Ajoute 1 pour chaque caractère de s, soustrais 1 pour chaque caractère de t, puis vérifie que chaque compteur est égal à 0. Parcours les chaînes caractère par caractère, et non octet par octet, afin qu’un caractère stocké sur plusieurs octets ne soit compté qu’une fois.

Pourquoi utiliser un seul tableau de compteurs au lieu de deux ?

Deux tableaux, un par chaîne, fonctionnent aussi : compte chaque chaîne, puis compare les tableaux. Un seul tableau qui s’incrémente pour s et se décrémente pour t utilise deux fois moins de mémoire et permet de renvoyer false dès qu’un compteur devient négatif, sans boucle de comparaison finale.

Python

def isAnagram(s, t):
    # Écrivez le code ici

Cas de test

Cas 1

Cas 2

Cas 3

Entrée

s = "listen"
t = "silent"

Attendu

true