Valid Anagram

Description

[EN]

Given two strings s and t, return true if the two strings are anagrams of each other, otherwise return false. An anagram is a string that contains the exact same characters as another string, but the order of the characters can be different.

[FR]

Étant donné deux chaînes de caractères s et t, le programme retourne true si t est une anagramme de s, et false dans le cas contraire. Deux chaînes sont considérées comme des anagrammes si elles contiennent exactement les mêmes caractères, avec la même fréquence, mais potentiellement dans un ordre différent. Par exemple :

• s = "listen" et t = "silent" sont des anagrammes.

• s = "hello" et t = "world" ne sont pas des anagrammes.

Approche initiale

Une première méthode consiste à trier les deux chaines de caractères puis vérifier si les résultats des deux tris sont égaux:

• Complexité temporelle :

  • La complexité totale est dominée par l'opération de tri, soit O(nlogn).

• Complexité spatiale :

  • Deux tableaux de caractères sOrdered et tOrdered sont créés, repectivement de taille m et n . La complexité spatiale est donc O(max(n,m)).

Approche optimisée: Utilisation d'une HashMap

• Validation de la longueur des chaînes :

  • Si les chaînes s et t n'ont pas la même longueur, elles ne peuvent pas être des anagrammes. On retourne immédiatement false.

• Création des HashMaps :

  • Deux HashMaps, charCountS et charCountT, sont utilisées pour stocker le nombre d'occurrences de chaque caractère dans s et t.

• Parcours des chaînes :

  • En parcourant les caractères des deux chaînes simultanément :

    • On incrémente le compteur pour le caractère courant dans la HashMap correspondant à chaque chaîne.

• Comparaison des HashMaps :

  • Une fois le comptage terminé, on compare les deux HashMaps avec la méthode equals.

  • Si les deux HashMaps sont identiques (mêmes clés avec les mêmes valeurs), s et t sont des anagrammes, et la méthode retourne true.

  • Sinon, elle retourne false.

• Complexité temporelle :

  • La complexité totale est de O(n).

• Complexité spatiale :

  • La complexité spatiale est O(1), puisqu'il y a au maximum 26 caractères différents