Programme Java pour vérifier si deux chaînes sont des anagrammes | Programme Anagramme
Publié: 2021-07-23Table des matières
Faits moins connus sur Java
Étant l'un des langages de programmation les plus durables, Java est utilisé dans le monde entier en raison de ses fonctionnalités robustes et flexibles. La stabilité et la polyvalence de Java en ont fait l'un des langages de programmation les plus recherchés. Cependant, il existe plusieurs faits moins connus sur ce langage de programmation sécurisé. Apprenons à en connaître quelques-uns.
- Oak est le nom original de Java.
- Vous pouvez gagner beaucoup en apprenant ce langage de programmation.
- Java est le deuxième langage de programmation le plus peuplé au monde, le premier étant le C.
- Environ 3 milliards d'appareils à travers le monde fonctionnent sur Java.
- Java est un langage de programmation sensible à la casse. c'est-à-dire que "Final" et "final" ne sont pas les mêmes dans le code Java. En savoir plus sur les raisons pour lesquelles Java est si populaire auprès des développeurs.
Un aperçu de l'anagramme
Si une chaîne est transformée en une autre chaîne en réorganisant ses caractères, on dit que les deux chaînes sont les anagrammes l'une de l'autre. Cependant, le nombre de caractères dans la chaîne initiale et la chaîne obtenue doivent être identiques. Pour mieux comprendre le concept d'anagramme, considérons deux chaînes, 'dieu' et 'chien'.
Les chaînes 'dieu' et 'chien' sont des anagrammes l'une de l'autre car la première chaîne peut être réarrangée pour obtenir la seconde simplement en intervertissant les positions des caractères 'd' et 'g'. Pour deux chaînes d'entrée quelconques, la fréquence de chaque caractère est calculée pour vérifier si les chaînes sont des anagrammes l'une de l'autre ou non. Ainsi, un anagramme d'une chaîne peut être défini comme n'importe quelle autre chaîne qui a les mêmes caractères avec la même fréquence que dans la chaîne d'entrée dans n'importe quelle séquence.
Algorithme pour le programme Anagram en Java
Étape 1 : Définissez les deux chaînes d'entrée.
Étape 2 : La longueur de chaque chaîne est déterminée. Les chaînes d'entrée ne sont pas des anagrammes les unes des autres si elles ont des longueurs de chaîne différentes.
Étape 3 : Si les chaînes ont la même longueur, les caractères de la chaîne sont convertis en lettres minuscules pour faciliter la comparaison.
Étape 4 : Les caractères de la chaîne sont soit triés par des fonctions intégrées, soit convertis en un tableau de caractères, puis triés.
Étape 5 : L'égalité du tableau de caractères trié est vérifiée.
Implémentation du programme Anagram en Java
Il existe plusieurs solutions pour implémenter un code permettant de savoir si deux chaînes sont des anagrammes ou non. Pour chaque solution discutée dans les sections suivantes, l'étape 2 de l'algorithme décrit ci-dessus constitue la base et facilite la sortie anticipée si les longueurs de chaîne ne correspondent pas. Dans les sections suivantes, nous allons en savoir plus sur les différents types d'écriture d'un code pour la logique des anagrammes.
Approche de tri
Les caractères de chaque chaîne d'entrée peuvent être triés pour obtenir deux tableaux de caractères normalisés. Si les tableaux normalisés des deux chaînes d'entrée sont identiques, les chaînes sont considérées comme des anagrammes l'une de l'autre et vice versa.
La compréhension et la mise en œuvre de ce code sont plus faciles. La complexité temporelle de la solution ci-dessus est O(n log n) et un espace supplémentaire est nécessaire pour stocker les tableaux de caractères des chaînes d'entrée.
Apprenez des cours de développement de logiciels en ligne dans les meilleures universités du monde. Gagnez des programmes Executive PG, des programmes de certificat avancés ou des programmes de maîtrise pour accélérer votre carrière.
Approche de comptage pour la mise en œuvre de la logique d'anagramme
Dans cette approche, le nombre d'existences de chaque caractère dans les deux chaînes d'entrée est mesuré. Si la fréquence de chaque caractère dans les deux chaînes est identique, les chaînes sont des anagrammes l'une de l'autre.
Construisons un seul histogramme pour économiser de la mémoire. Dans la première chaîne, les comptes de chaque caractère sont incrémentés, tandis que les comptes sont décrémentés pour la seconde. Si le résultat final équilibre tout à zéro, alors les chaînes sont des anagrammes.
Cette solution s'exécute plus rapidement que la solution précédente et sa complexité temporelle est O(n). Cependant, un espace supplémentaire est nécessaire pour compter les caractères. Cette solution n'est pratiquement efficace que pour les chaînes avec une plage de caractères plus petite. Un autre fait de cette solution est qu'elle utilise un nombre limité de fonctions Java intégrées et augmente ainsi la longueur du code.
Paiement : Idées et sujets de projet Java
Déterminer les anagrammes en vérifiant avec MultiSet
L'utilisation de MultiSet, une collection qui facilite la comparaison indépendante de l'ordre avec des éléments identiques, simplifie le processus de comptage et de comparaison dans cette solution.
Chaque chaîne d'entrée est initialement convertie en un multiensemble de caractères, puis vérifiée pour la parité.
La complexité temporelle de cette solution est O(n). Il est similaire à l'approche de comptage pour déterminer les anagrammes. Cependant, cela peut fonctionner efficacement pour des cordes de plus grande longueur. De plus, le codage implique un plus grand nombre de fonctions de la bibliothèque Java.
Approche basée sur les lettres pour déterminer les anagrammes
Toutes les solutions discutées jusqu'à présent considèrent les caractères de ponctuation également comme faisant partie de la chaîne. De plus, ces solutions sont sensibles à la casse. L'approche basée sur les lettres implémente un code pour vérifier les chaînes d'entrée en fonction de la définition linguistique des anagrammes. Dans cette approche, les espaces blancs et les ponctuations ne sont pas considérés comme faisant partie de la chaîne d'entrée.
La première étape lors de la mise en œuvre d'une solution basée sur les lettres est l'élimination des caractères indésirables et la conversion de tous les caractères valides en lettres minuscules. Après cette étape, l'une des implémentations décrites ci-dessus peut être utilisée pour vérifier si les chaînes sont des anagrammes ou non.
Si vous souhaitez en savoir plus sur Java, le développement de logiciels full-stack, consultez le programme Executive PG de upGrad & IIIT-B en développement de logiciels - Spécialisation en développement Full Stack, conçu pour les professionnels en activité et offrant plus de 500 heures de formation rigoureuse. , 9+ projets et affectations, statut d'ancien de l'IIIT-B, projets de synthèse pratiques et aide à l'emploi avec les meilleures entreprises.
