Comment vérifier si deux mots sont des anagrammes

J’ai un programme qui vous montre si deux mots sont des anagrammes les uns des autres. Il y a quelques exemples qui ne fonctionneront pas correctement et j’apprécierais toute aide, même si ce n’est pas avancé, ce serait génial, car je suis programmeur de 1ère année. “schoolmaster” et “theclassroom” sont des anagrammes les uns des autres, mais quand je change “theclassroom” en “theclafsroom”, il dit toujours que ce sont des anagrammes, que fais-je mal?

import java.util.ArrayList; public class AnagramCheck { public static void main(Ssortingng args[]) { Ssortingng phrase1 = "tbeclassroom"; phrase1 = (phrase1.toLowerCase()).sortingm(); char[] phrase1Arr = phrase1.toCharArray(); Ssortingng phrase2 = "schoolmaster"; phrase2 = (phrase2.toLowerCase()).sortingm(); ArrayList phrase2ArrList = convertSsortingngToArraylist(phrase2); if (phrase1.length() != phrase2.length()) { System.out.print("There is no anagram present."); } else { boolean isFound = true; for (int i=0; i<phrase1Arr.length; i++) { for(int j = 0; j < phrase2ArrList.size(); j++) { if(phrase1Arr[i] == phrase2ArrList.get(j)) { System.out.print("There is a common element.\n"); isFound = ; phrase2ArrList.remove(j); } } if(isFound == false) { System.out.print("There are no anagrams present."); return; } } System.out.printf("%s is an anagram of %s", phrase1, phrase2); } } public static ArrayList convertSsortingngToArraylist(Ssortingng str) { ArrayList charList = new ArrayList(); for(int i = 0; i<str.length();i++){ charList.add(str.charAt(i)); } return charList; } } 

L’algorithme le plus rapide serait de mapper chacun des 26 caractères anglais à un nombre premier unique. Calculez ensuite le produit de la chaîne. Par le théorème fondamental de l’arithmétique, 2 chaînes sont des anagrammes si et seulement si leurs produits sont les mêmes.

Deux mots sont des anagrammes les uns des autres s’ils contiennent le même nombre de caractères et les mêmes caractères. Vous devez seulement sortinger les caractères dans l’ordre lexicographique et comparer si Ssortingng a est égal à Ssortingng b à toutes les étapes.

Voici un exemple de code. Consultez les Arrays de l’API pour comprendre ce qui se passe ici.

 public boolean isAnagram(Ssortingng firstWord, Ssortingng secondWord) { char[] word1 = firstWord.replaceAll("[\\s]", "").toCharArray(); char[] word2 = secondWord.replaceAll("[\\s]", "").toCharArray(); Arrays.sort(word1); Arrays.sort(word2); return Arrays.equals(word1, word2); } 

Si vous sortingez un tableau, la solution devient O (n log n). mais si vous utilisez un hashmap, c’est O (n). testé et fonctionnel.

 char[] word1 = "test".toCharArray(); char[] word2 = "tes".toCharArray(); Map lettersInWord1 = new HashMap(); for (char c : word1) { int count = 1; if (lettersInWord1.containsKey(c)) { count = lettersInWord1.get(c) + 1; } lettersInWord1.put(c, count); } for (char c : word2) { int count = -1; if (lettersInWord1.containsKey(c)) { count = lettersInWord1.get(c) - 1; } lettersInWord1.put(c, count); } for (char c : lettersInWord1.keySet()) { if (lettersInWord1.get(c) != 0) { return false; } } return true; 

Voici une solution O (n) simple et rapide sans utiliser de sorting ou de boucles multiples ou de cartes de hachage. Nous incrémentons le nombre de chaque caractère du premier tableau et décrémentons le nombre de chaque caractère du deuxième tableau. Si le tableau de nombres résultant est plein de zéros, les chaînes sont des anagrammes. Peut être étendu pour inclure d’autres caractères en augmentant la taille du tableau de comptes.

 class AnagramsFaster{ private static boolean compare(Ssortingng a, Ssortingng b){ char[] aArr = a.toLowerCase().toCharArray(), bArr = b.toLowerCase().toCharArray(); if (aArr.length != bArr.length) return false; int[] counts = new int[26]; // An array to hold the number of occurrences of each character for (int i = 0; i < aArr.length; i++){ counts[aArr[i]-97]++; // Increment the count of the character at i counts[bArr[i]-97]--; // Decrement the count of the character at i } // If the strings are anagrams, the counts array will be full of zeros for (int i = 0; i<26; i++) if (counts[i] != 0) return false; return true; } public static void main(String[] args){ System.out.println(compare(args[0], args[1])); } } 

Beaucoup de gens ont présenté des solutions, mais je veux juste parler de la complexité algorithmique de certaines des approches communes:

  • Le simple “sortinger les caractères en utilisant Arrays.sort() ” va être O(N log N) .

  • Si vous utilisez le sorting par base, cela se réduit à O(N) avec un espace O(M) , où M est le nombre de caractères distincts de l’alphabet. (C’est 26 en anglais … mais en théorie, nous devrions considérer les anagrammes multilingues.)

  • Le “compter les caractères” en utilisant un tableau de comptes est aussi O(N) … et plus rapide que le sorting par base parce que vous n’avez pas besoin de reconstruire la chaîne sortingée. L’utilisation de l’espace sera O(M) .

  • Un “compter les caractères” en utilisant un dictionnaire, un hashmap, un treemap ou équivalent sera plus lent que l’approche du tableau, à moins que l’alphabet ne soit énorme.

  • L’approche élégante “product-of-Prime” est malheureusement O(N^2) dans le pire des cas. En effet, pour des mots ou des phrases assez longs, le produit des nombres premiers ne tiendra pas long . Cela signifie que vous devez utiliser BigInteger , et N fois multipliant un BigInteger par une petite constante est O(N^2) .

    Pour un grand alphabet hypothétique, le facteur d’échelle sera important. L’utilisation d’espace dans le pire des cas pour contenir le produit des nombres premiers en tant que BigInteger est (je pense) O(N*logM) .

  • Une approche basée sur le hashcode est généralement O(N) si les mots ne sont pas des anagrammes. Si les codes de hachage sont égaux, vous devez toujours effectuer un test d’anagramme approprié. Donc, ce n’est pas une solution complète.

O (n) solution sans aucune sorte de sorting et en utilisant une seule carte.

 public boolean isAnagram(Ssortingng leftSsortingng, Ssortingng rightSsortingng) { if (leftSsortingng == null || rightSsortingng == null) { return false; } else if (leftSsortingng.length() != rightSsortingng.length()) { return false; } Map occurrencesMap = new HashMap<>(); for(int i = 0; i < leftString.length(); i++){ char charFromLeft = leftString.charAt(i); int nrOfCharsInLeft = occurrencesMap.containsKey(charFromLeft) ? occurrencesMap.get(charFromLeft) : 0; occurrencesMap.put(charFromLeft, ++nrOfCharsInLeft); char charFromRight = rightString.charAt(i); int nrOfCharsInRight = occurrencesMap.containsKey(charFromRight) ? occurrencesMap.get(charFromRight) : 0; occurrencesMap.put(charFromRight, --nrOfCharsInRight); } for(int occurrencesNr : occurrencesMap.values()){ if(occurrencesNr != 0){ return false; } } return true; } 

et solution moins générique mais un peu plus rapide. Vous devez placer votre alphabet ici:

 public boolean isAnagram(Ssortingng leftSsortingng, Ssortingng rightSsortingng) { if (leftSsortingng == null || rightSsortingng == null) { return false; } else if (leftSsortingng.length() != rightSsortingng.length()) { return false; } char letters[] = {'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z'}; Map occurrencesMap = new HashMap<>(); for (char l : letters) { occurrencesMap.put(l, 0); } for(int i = 0; i < leftString.length(); i++){ char charFromLeft = leftString.charAt(i); Integer nrOfCharsInLeft = occurrencesMap.get(charFromLeft); occurrencesMap.put(charFromLeft, ++nrOfCharsInLeft); char charFromRight = rightString.charAt(i); Integer nrOfCharsInRight = occurrencesMap.get(charFromRight); occurrencesMap.put(charFromRight, --nrOfCharsInRight); } for(Integer occurrencesNr : occurrencesMap.values()){ if(occurrencesNr != 0){ return false; } } return true; } 

Nous marchons deux chaînes de même longueur et suivons les différences entre elles. Nous ne nous soucions pas des différences, nous voulons simplement savoir si elles ont les mêmes caractères ou non. Nous pouvons le faire dans O (n / 2) sans aucun post-traitement (ou beaucoup de nombres premiers).

 public class TestAnagram { public static boolean isAnagram(Ssortingng first, Ssortingng second) { Ssortingng positive = first.toLowerCase(); Ssortingng negative = second.toLowerCase(); if (positive.length() != negative.length()) { return false; } int[] counts = new int[26]; int diff = 0; for (int i = 0; i < positive.length(); i++) { int pos = (int) positive.charAt(i) - 97; // convert the char into an array index if (counts[pos] >= 0) { // the other ssortingng doesn't have this diff++; // an increase in differences } else { // it does have it diff--; // a decrease in differences } counts[pos]++; // track it int neg = (int) negative.charAt(i) - 97; if (counts[neg] <= 0) { // the other string doesn't have this diff++; // an increase in differences } else { // it does have it diff--; // a decrease in differences } counts[neg]--; // track it } return diff == 0; } public static void main(String[] args) { System.out.println(isAnagram("zMarry", "zArmry")); // true System.out.println(isAnagram("basiparachromatin", "marsipobranchiata")); // true System.out.println(isAnagram("hydroxydeoxycorticosterones", "hydroxydesoxycorticosterone")); // true System.out.println(isAnagram("hydroxydeoxycorticosterones", "hydroxydesoxycorticosterons")); // false System.out.println(isAnagram("zArmcy", "zArmry")); // false } } 

Oui, ce code dépend du jeu de caractères anglais ASCII en minuscules, mais il ne devrait pas être difficile de le modifier en d'autres langues. Vous pouvez toujours utiliser une carte [Caractère, Int] pour suivre les mêmes informations, cela ne sera que plus lent.

En utilisant plus de mémoire (un HashMap contenant au plus N / 2 éléments), nous n’avons pas besoin de sortinger les chaînes.

 public static boolean areAnagrams(Ssortingng one, Ssortingng two) { if (one.length() == two.length()) { Ssortingng s0 = one.toLowerCase(); Ssortingng s1 = two.toLowerCase(); HashMap chars = new HashMap(one.length()); Integer count; for (char c : s0.toCharArray()) { count = chars.get(c); count = Integer.valueOf(count != null ? count + 1 : 1); chars.put(c, count); } for (char c : s1.toCharArray()) { count = chars.get(c); if (count == null) { return false; } else { count--; chars.put(c, count); } } for (Integer i : chars.values()) { if (i != 0) { return false; } } return true; } else { return false; } } 

Cette fonction est en cours d’exécution dans O (N) … au lieu de O (NlogN) pour la solution qui sortinge les chaînes. Si je supposais que vous n’utiliseriez que des caractères alphabétiques, je ne pourrais utiliser qu’un tableau de 26 pouces (de a à z sans accents ni décorations) au lieu du hashmap.

Si nous définissons cela: N = | un | + | deux | nous faisons une itération sur N (une fois sur un pour incrémenter les compteurs et une fois pour les décrémenter sur deux). Ensuite, pour vérifier les totaux, nous parcourons N / 2.

Les autres algorithmes décrits ont un avantage: ils n’utilisent pas de mémoire supplémentaire en supposant qu’Arrays.sort utilise des versions in situ de QuickSort ou de sorting par fusion. Mais puisque nous parlons d’anagrammes, je suppose que nous parlons de langages humains, ainsi les mots ne devraient pas être assez longs pour donner des problèmes de mémoire.

  /* * To change this template, choose Tools | Templates * and open the template in the editor. */ package Algorithms; import java.util.ArrayList; import java.util.Arrays; import java.util.HashMap; import javax.swing.JOptionPane; /** * * @author Mokhtar */ public class Anagrams { //Write aprogram to check if two words are anagrams public static void main(Ssortingng[] args) { Anagrams an=new Anagrams(); ArrayList l=new ArrayList(); Ssortingng result=JOptionPane.showInputDialog("How many words to test anagrams"); if(Integer.parseInt(result) >1) { for(int i=0;i l) { boolean isanagrams=true; ArrayList anagrams = null; HashMap> map = new HashMap>(); for(int i=0;i(); anagrams.add(word); map.put(sortedWord, anagrams); } for(int h=0;h 

Je suis un développeur C ++ et le code ci-dessous est en C ++. Je pense que la manière la plus rapide et la plus simple de procéder serait la suivante:

Créez un vecteur de taille 26, avec tous les emplacements initialisés à 0 et placez chaque caractère de la chaîne dans la position appropriée dans le vecteur. Rappelez-vous que le vecteur est dans l’ordre alphabétique et donc si la première lettre de la chaîne est z, elle irait dans myvector [26]. Note: Ceci peut être fait en utilisant des caractères ASCII, donc votre code ressemblera à ceci:

 ssortingng s = zadg; for(int i =0; i < s.size(); ++i){ myvector[s[i] - 'a'] = myvector['s[i] - 'a'] + 1; } 

Donc, insérer tous les éléments prendrait O (n) time car vous ne traverseriez que la liste une fois. Vous pouvez maintenant faire exactement la même chose pour la deuxième chaîne et cela prendrait aussi O (n) temps. Vous pouvez ensuite comparer les deux vecteurs en vérifiant si les compteurs de chaque emplacement sont identiques. Si tel est le cas, cela signifie que vous avez le même nombre de caractères dans les deux cordes et que ce sont donc des anagrammes. La comparaison des deux vecteurs devrait également prendre le temps O (n) car vous ne la traversez qu'une fois.

Remarque: le code ne fonctionne que pour un seul mot de caractères. Si vous avez des espaces, des nombres et des symboles, vous pouvez simplement créer un vecteur de taille 96 (caractères ASCII 32-127) et au lieu de dire - "a" vous diriez - "car le caractère espace est le premier du Liste de caractères ASCII.

J'espère que ça aide. Si j'ai fait une erreur quelque part, veuillez laisser un commentaire.

Beaucoup de réponses compliquées ici. Sur la base de la réponse acceptée et du commentaire mentionnant le problème ‘ac’ – ‘bb’ en supposant que A = 1 B = 2 C = 3, nous pourrions simplement utiliser le carré de chaque entier représentant un caractère et résoudre le problème:

 public boolean anagram(Ssortingng s, Ssortingng t) { if(s.length() != t.length()) return false; int value = 0; for(int i = 0; i < s.length(); i++){ value += ((int)s.charAt(i))^2; value -= ((int)t.charAt(i))^2; } return value == 0; } 

Merci d’avoir signalé pour faire des commentaires, tout en faisant un commentaire, j’ai trouvé qu’il y avait une logique incorrecte. J’ai corrigé la logique et ajouté un commentaire pour chaque morceau de code.

 // Time complexity: O(N) where N is number of character in Ssortingng // Required space :constant space. // will work for ssortingng that contains ASCII chars private static boolean isAnagram(Ssortingng s1, Ssortingng s2) { // if length of both ssortingng's are not equal then they are not anagram of each other if(s1.length() != s2.length())return false; // array to store the presence of a character with number of occurrences. int []seen = new int[256]; // initialize the array with zero. Do not need to initialize specifically since by default element will initialized by 0. // Added this is just increase the readability of the code. Arrays.fill(seen, 0); // convert each ssortingng to lower case if you want to make ABC and aBC as anagram, other wise no need to change the case. s1 = s1.toLowerCase(); s2 = s2.toLowerCase(); // iterate through the first ssortingng and count the occurrences of each character for(int i =0; i < s1.length(); i++){ seen[s1.charAt(i)] = seen[s1.charAt(i)] +1; } // iterate through second string and if any char has 0 occurrence then return false, it mean some char in s2 is there that is not present in s1. // other wise reduce the occurrences by one every time . for(int i =0; i < s2.length(); i++){ if(seen[s2.charAt(i)] ==0)return false; seen[s2.charAt(i)] = seen[s2.charAt(i)]-1; } // now if both string have same occurrence of each character then the seen array must contains all element as zero. if any one has non zero element return false mean there are // some character that either does not appear in one of the string or/and mismatch in occurrences for(int i = 0; i < 256; i++){ if(seen[i] != 0)return false; } return true; } 

Voici ma solution. Explosez d’abord les chaînes de caractères dans des tableaux de caractères, puis sortingez-les et comparez-les si elles sont égales ou non. Je suppose que la complexité temporelle de ce code est O (a + b). Si a = b on peut dire O (2A)

 public boolean isAnagram(Ssortingng s1, Ssortingng s2) { SsortingngBuilder sb1 = new SsortingngBuilder(); SsortingngBuilder sb2 = new SsortingngBuilder(); if (s1.length() != s2.length()) return false; char arr1[] = s1.toCharArray(); char arr2[] = s2.toCharArray(); Arrays.sort(arr1); Arrays.sort(arr2); for (char c : arr1) { sb1.append(c); } for (char c : arr2) { sb2.append(c); } System.out.println(sb1.toSsortingng()); System.out.println(sb2.toSsortingng()); if (sb1.toSsortingng().equals(sb2.toSsortingng())) return true; else return false; } 

Une réponse similaire a peut-être été postée en C ++, la voici de nouveau en Java. Notez que la manière la plus élégante serait d’utiliser un Trie pour stocker les caractères dans un ordre sortingé, mais c’est une solution plus complexe. Une manière consiste à utiliser un hashset pour stocker tous les mots que nous comparons, puis à les comparer un par un. Pour les comparer, créez un tableau de caractères avec l’index représentant la valeur ANCII des caractères (en utilisant un normalisateur car la valeur ANCII de ‘a’ est 97) et la valeur représentant le nombre d’occurrences de ce caractère. Cela se déroulera dans O (n) time et utilisera O (m * z) espace où m est la taille du currentWord et z la taille du Word stocké, les deux pour lesquels nous créons un Char [].

 public static boolean makeAnagram(Ssortingng currentWord, Ssortingng storedWord){ if(currentWord.length() != storedWord.length()) return false;//words must be same length Integer[] currentWordChars = new Integer[totalAlphabets]; Integer[] storedWordChars = new Integer[totalAlphabets]; //create a temp Arrays to compare the words storeWordCharacterInArray(currentWordChars, currentWord); storeWordCharacterInArray(storedWordChars, storedWord); for(int i = 0; i < totalAlphabets; i++){ //compare the new word to the current charList to see if anagram is possible if(currentWordChars[i] != storedWordChars[i]) return false; } return true;//and store this word in the HashSet of word in the Heap } //for each word store its characters public static void storeWordCharacterInArray(Integer[] characterList, String word){ char[] charCheck = word.toCharArray(); for(char c: charCheck){ Character cc = c; int index = cc.charValue()-indexNormalizer; characterList[index] += 1; } } 

Jusqu’à présent, toutes les solutions proposées fonctionnent avec des éléments de caractères distincts, et non des points de code. J’aimerais proposer deux solutions pour gérer correctement les paires de substitution (il s’agit des caractères de U + 10000 à U + 10FFFF , composés de deux éléments de caractère).

1) Une solution O (n logn) à une ligne qui utilise le CharSequence.codePoints() Java 8 CharSequence.codePoints() :

 static boolean areAnagrams(CharSequence a, CharSequence b) { return Arrays.equals(a.codePoints().sorted().toArray(), b.codePoints().sorted().toArray()); } 

2) Solution moins élégante O (n) (en fait, ce ne sera plus rapide que pour les longues chaînes avec de faibles chances d’être des anagrammes) :

 static boolean areAnagrams(CharSequence a, CharSequence b) { int len = a.length(); if (len != b.length()) return false; // collect codepoint occurrences in "a" Map ocr = new HashMap<>(64); a.codePoints().forEach(c -> ocr.merge(c, 1, Integer::sum)); // for each codepoint in "b", look for matching occurrence for (int i = 0, c = 0; i < len; i += Character.charCount(c)) { int cc = ocr.getOrDefault((c = Character.codePointAt(b, i)), 0); if (cc == 0) return false; ocr.put(c, cc - 1); } return true; } 

Comment un mathématicien pourrait penser au problème avant d’écrire un code :

  1. La relation “sont des anagrammes” entre les chaînes est une relation d’équivalence , divise donc l’ensemble de toutes les chaînes en classes d’équivalence.
  2. Supposons que nous ayons une règle pour choisir un représentant (berceau) de chaque classe, puis il est facile de tester si deux classes sont identiques en comparant leurs représentants.
  3. Un représentant évident pour un ensemble de chaînes est “le plus petit élément par ordre lexicographique “, qui est facile à calculer à partir de n’importe quel élément en le sortingant. Par exemple, le représentant de la classe d’anagramme contenant «chapeau» est «aht».

Dans votre exemple, “maître d’école” et “classe” sont des anagrammes car elles sont toutes deux dans la classe des anagrammes avec crèche “acehlmoorsst”.

En pseudocode:

 >>> def crib(word): ... return sorted(word) ... >>> crib("schoolmaster") == crib("theclassroom") True 
 import java.util.ArrayList; import java.util.List; import java.util.Map; import java.util.TreeMap; /** * Check if Anagram by Prime Number Logic * @author Pallav * */ public class Anagram { public static void main(Ssortingng args[]) { System.out.println(isAnagram(args[0].toUpperCase(), args[1].toUpperCase())); } /** * * @param word : The Ssortingng 1 * @param anagram_word : The Ssortingng 2 with which Anagram to be verified * @return true or false based on Anagram */ public static Boolean isAnagram(Ssortingng word, Ssortingng anagram_word) { //If length is different return false if (word.length() != anagram_word.length()) { return false; } char[] words_char = word.toCharArray();//Get the Char Array of First Ssortingng char[] anagram_word_char = anagram_word.toCharArray();//Get the Char Array of Second Ssortingng int words_char_num = 1;//Initialize Multiplication Factor to 1 int anagram_word_num = 1;//Initialize Multiplication Factor to 1 for Ssortingng 2 Map wordPrimeMap = wordPrimeMap();//Get the Prime numbers Mapped to each alphabets in English for (int i = 0; i < words_char.length; i++) { words_char_num *= wordPrimeMap.get(words_char[i]);//get Multiplication value for String 1 } for (int i = 0; i < anagram_word_char.length; i++) { anagram_word_num *= wordPrimeMap.get(anagram_word_char[i]);//get Multiplication value for String 2 } return anagram_word_num == words_char_num; } /** * Get the Prime numbers Mapped to each alphabets in English * @return */ public static Map wordPrimeMap() { List primes = primes(26); int k = 65; Map map = new TreeMap(); for (int i = 0; i < primes.size(); i++) { Character character = (char) k; map.put(character, primes.get(i)); k++; } // System.out.println(map); return map; } /** * get first N prime Numbers where Number is greater than 2 * @param N : Number of Prime Numbers * @return */ public static List primes(Integer N) { List primes = new ArrayList(); primes.add(2); primes.add(3); int n = 5; int k = 0; do { boolean is_prime = true; for (int i = 2; i <= Math.sqrt(n); i++) { if (n % i == 0) { is_prime = false; break; } } if (is_prime == true) { primes.add(n); } n++; // System.out.println(k); } while (primes.size() < N); // } return primes; } } 

À mon humble avis, la solution la plus efficace a été fournie par @Siguza, je l’ai étendue pour couvrir les chaînes avec un espace, par exemple: “William Shakespeare”, “Je suis un lecteur faible”, “Maître d’école”,

 public int getAnagramScore(Ssortingng word, Ssortingng anagram) { if (word == null || anagram == null) { throw new NullPointerException("Both, word and anagram, must be non-null"); } char[] wordArray = word.sortingm().toLowerCase().toCharArray(); char[] anagramArray = anagram.sortingm().toLowerCase().toCharArray(); int[] alphabetCountArray = new int[26]; int reference = 'a'; for (int i = 0; i < wordArray.length; i++) { if (!Character.isWhitespace(wordArray[i])) { alphabetCountArray[wordArray[i] - reference]++; } } for (int i = 0; i < anagramArray.length; i++) { if (!Character.isWhitespace(anagramArray[i])) { alphabetCountArray[anagramArray[i] - reference]--; } } for (int i = 0; i < 26; i++) if (alphabetCountArray[i] != 0) return 0; return word.length(); } 

Une autre solution sans sorting.

 public static boolean isAnagram(Ssortingng s1, Ssortingng s2){ //case insensitive anagram SsortingngBuffer sb = new SsortingngBuffer(s2.toLowerCase()); for (char c: s1.toLowerCase().toCharArray()){ if (Character.isLetter(c)){ int index = sb.indexOf(Ssortingng.valueOf(c)); if (index == -1){ //char does not exist in other s2 return false; } sb.deleteCharAt(index); } } for (char c: sb.toSsortingng().toCharArray()){ //only allow whitespace as left overs if (!Character.isWhitespace(c)){ return false; } } return true; } 

L’approche de sorting n’est pas la meilleure. Il prend O (n) espace et O (nlogn) temps. À la place, créez une carte de hachage des caractères et comptez-les (incrémentez les caractères qui apparaissent dans la première chaîne et décrémentez les caractères qui apparaissent dans la deuxième chaîne). Quand un compte atteint zéro, supprimez-le du hachage. Enfin, si deux chaînes sont des anagrammes, alors la table de hachage sera vide à la fin – sinon elle ne sera pas vide.

Quelques notes importantes: (1) Ignorer les lettres et (2) Ignorer les espaces blancs.

Voici l’parsing détaillée et l’implémentation en C #: Tester si deux chaînes sont des anagrammes

Une méthode simple pour déterminer si la chaîne de test est un anagramme de la chaîne de base.

 private static boolean isAnagram(Ssortingng baseSsortingng, Ssortingng testSsortingng){ //Assume that there are no empty spaces in either ssortingng. if(baseSsortingng.length() != testSsortingng.length()){ System.out.println("The 2 given words cannot be anagram since their lengths are different"); return false; } else{ if(baseSsortingng.length() == testSsortingng.length()){ if(baseSsortingng.equalsIgnoreCase(testSsortingng)){ System.out.println("The 2 given words are anagram since they are identical."); return true; } else{ List list = new ArrayList<>(); for(Character ch : baseString.toLowerCase().toCharArray()){ list.add(ch); } System.out.println("List is : "+ list); for(Character ch : testString.toLowerCase().toCharArray()){ if(list.contains(ch)){ list.remove(ch); } } if(list.isEmpty()){ System.out.println("The 2 words are anagrams"); return true; } } } } return false; } 

Désolé, la solution est en C #, mais je pense que les différents éléments utilisés pour arriver à la solution sont assez intuitifs. Légère mise au point requirejse pour les mots coupés, mais pour les mots normaux, cela devrait fonctionner correctement.

  internal bool isAnagram(ssortingng input1,ssortingng input2) { Dictionary outChars = AddToDict(input2.ToLower().Replace(" ", "")); input1 = input1.ToLower().Replace(" ",""); foreach(char c in input1) { if (outChars.ContainsKey(c)) { if (outChars[c] > 1) outChars[c] -= 1; else outChars.Remove(c); } } return outChars.Count == 0; } private Dictionary AddToDict(ssortingng input) { Dictionary inputChars = new Dictionary(); foreach(char c in input) { if(inputChars.ContainsKey(c)) { inputChars[c] += 1; } else { inputChars.Add(c, 1); } } return inputChars; } 

I saw that no one has used the “hashcode” approach to find out the anagrams. I found my approach little different than the approaches discussed above hence thought of sharing it. I wrote the below code to find the anagrams which works in O(n).

 /** * This class performs the logic of finding anagrams * @author ripudam * */ public class AnagramTest { public static boolean isAnagram(final Ssortingng word1, final Ssortingng word2) { if (word1 == null || word2 == null || word1.length() != word2.length()) { return false; } if (word1.equals(word2)) { return true; } final AnagramWrapper word1Obj = new AnagramWrapper(word1); final AnagramWrapper word2Obj = new AnagramWrapper(word2); if (word1Obj.equals(word2Obj)) { return true; } return false; } /* * Inner class to wrap the ssortingng received for anagram check to find the * hash */ static class AnagramWrapper { Ssortingng word; public AnagramWrapper(final Ssortingng word) { this.word = word; } @Override public boolean equals(final Object obj) { return hashCode() == obj.hashCode(); } @Override public int hashCode() { final char[] array = word.toCharArray(); int hashcode = 0; for (final char c : array) { hashcode = hashcode + (c * c); } return hashcode; } } } 

Je sais que c’est une vieille question. However, I’m hoping this can be of help to someone. The time complexity of this solution is O(n^2).

 public boolean areAnagrams(final Ssortingng word1, final Ssortingng word2) { if (word1.length() != word2.length()) return false; if (word1.equals(word2)) return true; if (word1.length() == 0 && word2.length() == 0) return true; Ssortingng secondWord = word2; for (int i = 0; i < word1.length(); i++) { if (secondWord.indexOf(word1.charAt(i)) == -1) return false; secondWord = secondWord.replaceFirst(word1.charAt(i) + "", ""); } if (secondWord.length() > 0) return false; return true; } 

Here is another approach using HashMap in Java

 public static boolean isAnagram(Ssortingng first, Ssortingng second) { if (first == null || second == null) { return false; } if (first.length() != second.length()) { return false; } return doCheckAnagramUsingHashMap(first.toLowerCase(), second.toLowerCase()); } private static boolean doCheckAnagramUsingHashMap(final Ssortingng first, final Ssortingng second) { Map counter = populateMap(first, second); return validateMap(counter); } private static boolean validateMap(Map counter) { for (int val : counter.values()) { if (val != 0) { return false; } } return true; } 

Here is the test case

 @Test public void anagramTest() { assertTrue(SsortingngUtil.isAnagram("keep" , "PeeK")); assertFalse(SsortingngUtil.isAnagram("Hello", "hell")); assertTrue(SsortingngUtil.isAnagram("SiLeNt caT", "LisTen cat")); } 
 private static boolean checkAnagram(Ssortingng s1, Ssortingng s2) { if (s1 == null || s2 == null) { return false; } else if (s1.length() != s2.length()) { return false; } char[] a1 = s1.toCharArray(); char[] a2 = s2.toCharArray(); int length = s2.length(); int s1Count = 0; int s2Count = 0; for (int i = 0; i < length; i++) { s1Count+=a1[i]; s2Count+=a2[i]; } return s2Count == s1Count ? true : false; } 

You should use something like that:

  for (int i...) { isFound = false; for (int j...) { if (...) { ... isFound = true; } } 

Default value for isFound should be false. Just it

A way to solve this – based on Sai Kiran’s answer..

 import java.util.Scanner; public class Anagram { public static void main(Ssortingng[] args) { Scanner sc = new Scanner(System.in); System.out.print("Enter first word : "); Ssortingng word1 = sc.nextLine(); System.out.print("Enter second word : "); Ssortingng word2 = sc.nextLine(); sc.close(); System.out.println("Is Anagram : " + isAnagram(word1, word2)); } private static boolean isAnagram(Ssortingng word1, Ssortingng word2) { if (word1.length() != word2.length()) { System.err.println("Words length didn't match!"); return false; } char ch1, ch2; int len = word1.length(), sumOfWord1Chars = 0, sumOfWord2Chars = 0; for (int i = 0; i < len; i++) { ch1 = word1.charAt(i); if (word2.indexOf(ch1) < 0) { System.err.println("'" + ch1 + "' not found in \"" + word2 + "\""); return false; } sumOfWord1Chars += word1.charAt(i); ch2 = word2.charAt(i); if (word1.indexOf(ch2) < 0) { System.err.println("'" + ch2 + "' not found in \"" + word1 + "\""); return false; } sumOfWord2Chars += word2.charAt(i); } if (sumOfWord1Chars != sumOfWord2Chars) { System.err .println("Sum of both words didn't match, ie, words having same characters but with different counts!"); return false; } return true; } } 

Works perfectly! But not a good approach because it runs in O(n^2)

 boolean isAnagram(Ssortingng A, Ssortingng B) { if(A.length() != B.length()) return false; A = A.toLowerCase(); B = B.toLowerCase(); for(int i = 0; i < A.length(); i++){ boolean found = false; for(int j = 0; j < B.length(); j++){ if(A.charAt(i) == B.charAt(j)){ found = true; break; } } if(!found){ return false; } } for(int i = 0; i < B.length(); i++){ boolean found = false; for(int j = 0; j < A.length(); j++){ if(A.charAt(j) == B.charAt(i)){ found = true; break; } } if(!found){ return false; } } int sum1 = 0, sum2 = 0; for(int i = 0; i < A.length(); i++){ sum1 += (int)A.charAt(i); sum2 += (int)B.charAt(i); } if(sum1 == sum2){ return true; } return false; } 

I had written this program in java. I think this might also help:

 public class Anagram { public static void main(Ssortingng[] args) { checkAnagram("listen", "silent"); } public static void checkAnagram(Ssortingng str1, Ssortingng str2) { boolean isAnagram = false; str1 = sortStr(str1); str2 = sortStr(str2); if (str1.equals(str2)) { isAnagram = true; } if (isAnagram) { System.out.println("Two ssortingngs are anagram"); } else { System.out.println("Two ssortingng are not anagram"); } } public static Ssortingng sortStr(Ssortingng str) { char[] strArr = str.toCharArray(); for (int i = 0; i < str.length(); i++) { for (int j = i + 1; j < str.length(); j++) { if (strArr[i] > strArr[j]) { char temp = strArr[i]; strArr[i] = strArr[j]; strArr[j] = temp; } } } Ssortingng output = Ssortingng.valueOf(strArr); return output; } }