242. Valid anagram

Sommaire

Description

Approche

Réflexions clés

Erreurs commises à éviter

Rectifications

En savoir plus sur la série Arrays and Hashing

Description

Given two strings s and t, return true if t is an anagram of s, and false otherwise. An anagram is a word or phrase formed by rearranging the letters of a different word or phrase, typically using all the original letters exactly once.

É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. Une anagramme est un mot ou une phrase formé en réarrangeant les lettres d'un autre mot ou d'une autre phrase, en utilisant généralement toutes les lettres originales une seule fois.

Approche

RAS

Réflexions clés

• Plusieurs solutions ont été implémentées par la communauté. La mienne a été incapable de sortir du prérequis d’avoir à parcourir toute la liste de caractères avant de vérifier la validité de l’anagramme. On peut dire ici qu’il s’agit d’un manque de créativité.

  • Ordonner les listes avant de les comparer dans leur entièreté.

• Créez une map non ordonnée count pour stocker les fréquences des caractères. La clé de la map représente un caractère, et la valeur représente sa fréquence.

Cette approche consiste à compter la fréquence des caractères dans une chaîne, puis à ajuster le compte en le décrémentant pour l'autre chaîne. Si les chaînes sont des anagrammes, la fréquence de chaque caractère s'annule, ce qui donne une map dont toutes les fréquences sont nulles.

La complexité temporelle de cette solution est O(n), où n est le nombre total de caractères dans les deux chaînes. Cette solution itère sur chaque caractère une fois pour compter les fréquences, puis compare les fréquences dans la map, ce qui en fait une solution efficace pour le problème.

Il convient toutefois de noter que cette approche a une complexité temporelle de O(n log n) en raison de l'opération de tri, où n est la longueur des chaînes de caractères.

Erreurs commises à éviter

• J'ai voulu, dans un premier temps, appliquer ce que j'ai appris avec les palindromes. Ce qui est une erreur parce que je ne cherche pas à savoir si les lettres sont, ou non, dans l'ordre inverse mais plutôt dans n’importe quel ordre.

Rectifications

• Changer

en

En savoir plus sur la série Arrays and Hashing

Cet article touche à sa fin, mais notre exploration des Arrays et Hashing ne fait que commencer. Ne manquez pas nos autres articles de la série pour approfondir vos connaissances, surtout si vous débutez ! Apprenez de mes expériences et progressez avec nous.