Vérifiez si deux chaînes sont des anagrammes en Java

1. Vue d'ensemble

Selon Wikipédia, un anagramme est un mot ou une expression formé en réorganisant les lettres d'un mot ou d'une phrase différent.

Nous pouvons généraliser cela dans le traitement des chaînes en disant qu'une anagramme d'une chaîne est une autre chaîne contenant exactement la même quantité de chaque caractère, dans n'importe quel ordre .

Dans ce tutoriel, nous allons examiner la détection d'anagrammes de chaînes entières où la quantité de chaque caractère doit être égale, y compris les caractères non alpha tels que les espaces et les chiffres. Par exemple, "! Low-salt!" et "hiboux-lat !!" seraient considérés comme des anagrammes car ils contiennent exactement les mêmes caractères.

2. Solution

Comparons quelques solutions qui peuvent décider si deux chaînes sont des anagrammes. Chaque solution vérifiera au début si les deux chaînes ont le même nombre de caractères. C'est un moyen rapide de sortir tôt car les entrées de différentes longueurs ne peuvent pas être des anagrammes .

Pour chaque solution possible, examinons la complexité de la mise en œuvre pour nous en tant que développeurs. Nous examinerons également la complexité temporelle du processeur, en utilisant la grande notation O.

3. Vérifier par tri

Nous pouvons réorganiser les caractères de chaque chaîne en triant leurs caractères, ce qui produira deux tableaux normalisés de caractères.

Si deux chaînes sont des anagrammes, leurs formes normalisées doivent être identiques.

En Java, nous pouvons d'abord convertir les deux chaînes en tableaux char [] . Ensuite, nous pouvons trier ces deux tableaux et vérifier l'égalité:

boolean isAnagramSort(String string1, String string2) { if (string1.length() != string2.length()) { return false; } char[] a1 = string1.toCharArray(); char[] a2 = string2.toCharArray(); Arrays.sort(a1); Arrays.sort(a2); return Arrays.equals(a1, a2); } 

Cette solution est facile à comprendre et à mettre en œuvre. Cependant, le temps d'exécution global de cet algorithme est O (n log n) car le tri d'un tableau de n caractères prend O (n log n) temps.

Pour que l'algorithme fonctionne, il doit faire une copie des deux chaînes d'entrée sous forme de tableaux de caractères, en utilisant un peu de mémoire supplémentaire.

4. Vérifier en comptant

Une autre stratégie consiste à compter le nombre d'occurrences de chaque caractère dans nos entrées. Si ces histogrammes sont égaux entre les entrées, alors les chaînes sont des anagrammes.

Pour économiser un peu de mémoire, construisons un seul histogramme. Nous incrémenterons le nombre de chaque caractère de la première chaîne et décrémenterons le nombre de chaque caractère de la seconde. Si les deux chaînes sont des anagrammes, le résultat sera que tout sera égal à 0.

L'histogramme a besoin d'une table de comptage de taille fixe avec une taille définie par la taille du jeu de caractères. Par exemple, si nous n'utilisons qu'un octet pour stocker chaque caractère, nous pouvons utiliser une taille de tableau de comptage de 256 pour compter l'occurrence de chaque caractère:

private static int CHARACTER_RANGE= 256; public boolean isAnagramCounting(String string1, String string2) { if (string1.length() != string2.length()) { return false; } int count[] = new int[CHARACTER_RANGE]; for (int i = 0; i < string1.length(); i++) { count[string1.charAt(i)]++; count[string2.charAt(i)]--; } for (int i = 0; i < CHARACTER_RANGE; i++) { if (count[i] != 0) { return false; } } return true; }

Cette solution est plus rapide avec la complexité temporelle de O (n) . Cependant, il a besoin d'espace supplémentaire pour le tableau de comptage. À 256 entiers, pour ASCII ce n'est pas trop mal.

Cependant, si nous devons augmenter CHARACTER_RANGE pour prendre en charge les jeux de caractères multi-octets tels que UTF-8, cela deviendrait très gourmand en mémoire. Par conséquent, ce n'est vraiment pratique que lorsque le nombre de caractères possibles est dans une petite plage.

Du point de vue du développement, cette solution contient plus de code à maintenir et utilise moins les fonctions de la bibliothèque Java.

5. Vérifiez avec MultiSet

Nous pouvons simplifier le processus de comptage et de comparaison en utilisant MultiSet . MultiSet est une collection qui prend en charge l'égalité indépendante de l'ordre avec des éléments en double. Par exemple, les multisets {a, a, b} et {a, b, a} sont égaux.

Pour utiliser Multiset , nous devons d'abord ajouter la dépendance Guava à notre fichier projet pom.xml :

 com.google.guava guava 28.1-jre  

Nous convertirons chacune de nos chaînes d'entrée en un MultiSet de caractères. Ensuite, nous vérifierons s'ils sont égaux:

boolean isAnagramMultiset(String string1, String string2) { if (string1.length() != string2.length()) { return false; } Multiset multiset1 = HashMultiset.create(); Multiset multiset2 = HashMultiset.create(); for (int i = 0; i < string1.length(); i++) { multiset1.add(string1.charAt(i)); multiset2.add(string2.charAt(i)); } return multiset1.equals(multiset2); } 

Cet algorithme résout le problème en temps O (n) sans avoir à déclarer un grand tableau de comptage.

C'est similaire à la solution de comptage précédente. Cependant, plutôt que d'utiliser une table de taille fixe pour compter, nous profitons de la classe MutlitSet pour simuler une table de taille variable, avec un compte pour chaque caractère.

Le code de cette solution utilise davantage les capacités de bibliothèque de haut niveau que notre solution de comptage.

6. Anagramme basé sur des lettres

Les exemples jusqu'à présent ne respectent pas strictement la définition linguistique d'un anagramme. C'est parce qu'ils considèrent les caractères de ponctuation comme faisant partie de l'anagramme et qu'ils sont sensibles à la casse.

Adaptons les algorithmes pour permettre une anagramme basée sur des lettres. Considérons uniquement le réarrangement des lettres insensibles à la casse, indépendamment des autres caractères tels que les espaces blancs et les ponctuations. Par exemple, "Un point décimal" et "Je suis un point en place". seraient des anagrammes les uns des autres.

Pour résoudre ce problème, nous pouvons d'abord prétraiter les deux chaînes d'entrée pour filtrer les caractères indésirables et convertir les lettres en minuscules. Ensuite, nous pouvons utiliser l'une des solutions ci-dessus (par exemple, la solution MultiSet ) pour vérifier les anagrammes sur les chaînes traitées:

String preprocess(String source) { return source.replaceAll("[^a-zA-Z]", "").toLowerCase(); } boolean isLetterBasedAnagramMultiset(String string1, String string2) { return isAnagramMultiset(preprocess(string1), preprocess(string2)); }

Cette approche peut être un moyen général de résoudre toutes les variantes des problèmes d'anagrammes. Par exemple, si nous voulons également inclure des chiffres, nous devons simplement ajuster le filtre de prétraitement.

7. Conclusion

Dans cet article, nous avons examiné trois algorithmes pour vérifier si une chaîne donnée est l'anagramme d'un autre, caractère pour caractère. Pour chaque solution, nous avons discuté des compromis entre la vitesse, la lisibilité et la taille de la mémoire requise.

Nous avons également examiné comment adapter les algorithmes pour vérifier les anagrammes au sens linguistique plus traditionnel. Nous y sommes parvenus en prétraitant les entrées en lettres minuscules.

Comme toujours, le code source de l'article est disponible à l'adresse over sur GitHub.