Anagrammes

Hourra ! Cet article marque le dernier défi de manipulation de chaînes de caractères dans cette section de ce cours. Nous avons parcouru un long chemin !

Dans ce défi, nous considérons deux façons de détecter les anagrammes en JavaScript.

Qu’est-ce qu’un anagramme ?

Un mot est dit anagramme d’un autre lorsqu’il peut être formé en réarrangeant les lettres de l’autre mot en utilisant chaque lettre une seule fois. Par exemple, listen est l’anagramme de silent.

Allons-y, n’est-ce pas ?

Vous devriez déjà avoir votre environnement de développement configuré pour ce cours. Mettez à jour votre dépôt cloné en exécutant la commande git pull. À l’intérieur du dossier Beginner, naviguez jusqu’au dossier isAnagram. Notre travail pour ce défi sera fait ici. Assurez-vous de suivre dans le fichierindex-START.js.

Le défi

Donné deux chaînes de caractères, écrivez un algorithme pour vérifier si elles sont des anagrammes l’une de l’autre. Retournez vrai si elles passent le test et faux si elles ne le passent pas. E.g

isAnagram('silent', 'listen') // should return true

Pensée algorithmique

Pour résoudre ce défi, nous écrivons une fonction qui accepterait deux paramètres c’est-à-dire les deux chaînes à comparer.

BeginnerTailwind.com Learn Tailwind CSS from Scratch

Au sein de la fonction, nous comparons les deux mots pour voir s’ils contiennent les mêmes caractères utilisés le même nombre de fois. Pour éviter les erreurs, nous aseptisons la chaîne de caractères se débarrassant ainsi des caractères indésirables et des espaces puisque ce ne sont pas des lettres de l’alphabet.

Nous convertissons également tous les caractères en une casse commune avant d’effectuer toute comparaison afin d’éviter les erreurs dues à une capitalisation variable. Vérifier que les deux mots sont de la même longueur est également très important car c’est un facteur primordial pour une comparaison valide.

Faisons cela.

Mise en œuvre du code

Nous allons maintenant considérer deux façons de mettre en œuvre notre solution en suivant notre logique algorithmique ci-dessus. Elles sont:

• Comparaison directe
• Comparaison par carte de caractères

Comparaison directe

Dans cette approche, nous définissons une fonction qui accepte deux paramètres c’est-à-dire les deux chaînes de caractères à comparer. Nous allons ensuite nettoyer les deux chaînes pour nous assurer que nous ne comparons que des lettres et dans un cas commun.

Nettoyage de la chaînePour nettoyer la chaîne, nous créons une fonction sanitizeString. Cette fonction accepte la chaîne de caractères à nettoyer comme paramètre et la utilise les méthodes .toLowerCase(), .replace(), .split(), .sort() et .join() pour manipuler la chaîne de caractères comme indiqué ci-dessous :

const sanitizeString = function (str) { return str.toLowerCase().replace(//g, '').split('').sort().join('');}

Décomposons un peu les choses :

• D’abord, nous convertissons toute la chaîne de caractères en minuscules en utilisant la méthode .toLowerCase().
• Puis, nous utilisons la méthode .replace() pour rechercher dans la chaîne en utilisant le modèle d’expression régulière spécifié et remplacer chaque caractère non alphabétique par une chaîne vide. Cela nous laisse uniquement des lettres. Pas d’espaces, pas de symboles !
• Puis, nous appelons .split() pour diviser la chaîne de caractères en un tableau de caractères.
• En utilisant la méthode .sort(), nous trions les lettres (éléments) dans le tableau par ordre alphabétique.
• Et enfin, nous réunissons le tableau de lettres maintenant ordonné alphabétiquement pour former à nouveau une chaîne de caractères.

Cette chaîne est ce que nous retournons comme chaîne assainie.

Smooth!** Right?**

Comparaison des chaînes assainiesL’assainissement de la chaîne comme fait ci-dessus est peut-être la partie la plus délicate de cette solution. Ensuite, nous nettoyons simplement les chaînes reçues à l’aide de la fonction sanitizeString et comparons les résultats. Si les deux chaînes correspondent, nous retournons true signifiant qu’elles passent comme des anagrammes. Si elles ne correspondent pas, nous retournons false signifiant qu’elles ne le sont pas.

Voir la solution complète ci-dessous :

function isAnagram(stringA, stringB) { const sanitizeString = function (str) { return str.toLowerCase().replace(//g, '').split('').sort().join(''); } return sanitizeString(stringA) == sanitizeString(stringB)}

Un de moins !** Devenons plus bizarres ! 😈**

Comme vous le verrez, l’approche que nous allons maintenant considérer suit une procédure plus progressive pour résoudre le problème.

Comparaison des cartes de caractères

Dans cette approche, nous générons d’abord une carte de caractères en utilisant notre fonction createCharMap.

Qu’est-ce qu’une carte de caractères ?

Comme utilisé dans ce contexte , un objet de carte de caractères est un objet qui fait correspondre chaque caractère d’une chaîne au nombre de fois qu’il apparaît dans la chaîne.

Création de la carte de caractèresDans notre createCharMap fonction ci-dessous, nous utilisons une boucle for…of pour itérer à travers chaque caractère de la chaîne de caractères reçue.

function createCharMap(text) { let charMap = {} for (let char of text) { if (charMap.hasOwnProperty(char)) { charMap++ } else { charMap = 1 } } return charMap}

Pour chaque caractère, nous vérifions si le caractère existe déjà comme propriété dans la carte de caractères charMap en utilisant la méthode .hasOwnProperty(). Si c’est le cas, nous incrémentons sa valeur et si ce n’est pas le cas, nous ajoutons le caractère comme propriété et mettons sa valeur à 1.

À la fin, nous retournons charMap qui est l’objet de carte de caractères.

Comparaison des cartes de caractèresMaintenant que nous avons une façon de générer les cartes de caractères, l’étape suivante sera de comparer les cartes de caractères pour les deux chaînes de caractères comme indiqué dans la solution complète ci-dessous :

function isAnagram(stringA, stringB) { function createCharMap(text) { let charMap = {} for (let char of text) { if (charMap.hasOwnProperty(char)) { charMap++ } else { charMap = 1 } } return charMap } if (stringA.length === stringB.length) { let stringAMap = createCharMap(stringA) let stringBMap = createCharMap(stringB) for (let char in stringAMap) { if (stringAMap !== stringBMap) { return false } } return true } else { return false }}

Notez que nous vérifions d’abord si la longueur des deux chaînes de caractères est égale. Si elles ne le sont pas, nous retournons false car c’est un indicateur qu’elles ne peuvent jamais être des anagrammes. Si elles le sont cependant, nous allons plus loin pour générer leurs cartes de caractères stockées comme variables stringAMap et stringBMap.

Puis, nous utilisons la boucle for…in pour comparer chaque caractère et valeur dans stringAMap à la valeur correspondante du caractère dans stringBMap. Si des valeurs ne correspondent pas, nous retournons false pour indiquer que les chaînes ne sont pas des anagrammes. Cependant, si toutes les valeurs correspondent, le test est passé et nous retournons true comme indication que les chaînes testées sont effectivement des anagrammes.

Nous l’avons fait. Une implémentation plus longue en effet mais c’est certainement une implémentation plus explicative.

Exécutons nos tests maintenant, d’accord ?

Tester la correction avec Jest

Pour tester chaque solution ci-dessus, exécutez la commande suivante depuis votre terminal:

npm run test isAnagram

• Comparaison directe

• Comparaison de cartes de caractères

Il semble que nous nous en sortons toujours très bien ! Nous avons réussi tous les tests.

Tester les performances avec JSPerf

Ici, nous effectuons un test de performance pour déterminer quelle solution est plus rapide. Retrouvez une capture d’écran du résultat ci-dessous :

D’après le résultat, nous observons que :

L’implémentation la plus rapide est l’approche de comparaison de carte de caractères et la méthode de comparaison directe bien que concise est environ 52% plus lente.

**Surprenant n’est-ce pas ? Les métriques ne mentent jamais cependant !**

Application pratique

Les algorithmes explorés ci-dessus peuvent être appliqués de différentes manières. Il s’agit notamment de :

• Cryptage
• Génération de mots de passe
• Affichage temporel fiable
• Codage d’interviews
• Génération de mnémoniques
• Jeux de mots
  

  Conclusion

En considérant les techniques et concepts explorés ci-dessus, nous avons appris des moyens précieux pour manipuler des chaînes de caractères afin de déterminer si elles sont des anagrammes. Nous avons également exploré divers domaines dans lesquels ces connaissances peuvent être directement utilisées.

Après avoir exécuté nos tests de performance, nous pouvons maintenant conclure que l’approche la plus optimale pour résoudre ce problème est la méthode de comparaison des cartes de caractères.

Lectures complémentaires

Pour en savoir plus sur les concepts et techniques mis en évidence ci-dessus, vous pouvez utiliser les liens suivants :

• Expressions régulières
• .replace()
• .split()
• .sort()
• .join()
• .hasOwnProperty()
• Pour…de vs pour…en boucle

On se retrouve dans la prochaine série d’articles axés sur les algorithmes de manipulation de tableaux!✌🏿

Vous aimez cet article ? Suivez @worldclassdev sur Twitter

.