Comment vérifier si deux mots sont des anagrammes

deux mots sont des anagrammes l'un de l'autre s'ils contiennent le même nombre de caractères et les mêmes caractères. Vous n'avez qu'à trier les caractères dans l'ordre lexicographique, et comparer si la chaîne a est égale à la chaîne b à toutes les étapes.

voici un exemple de code. Arrays dans l'API pour comprendre ce qui se passe ici.

public boolean isAnagram(String firstWord, String 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 triez l'un ou l'autre tableau, la solution devient O(N log n). mais si vous utilisez un hashmap, C'est O(n). testé et de travail.

char[] word1 = "test".toCharArray();
char[] word2 = "tes".toCharArray();

Map<Character, Integer> lettersInWord1 = new HashMap<Character, Integer>();

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 simple et rapide de O(n) sans utiliser de tri ou de boucles multiples ou des cartes de hachage. On incrémente le nombre de chaque personnage dans le premier tableau et décrémenter le nombre de chaque personnage dans le second tableau. Si le tableau de comptes 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 counts.

class AnagramsFaster{

    private static boolean compare(String a, String 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" trier les caractères en utilisant Arrays.sort() " l'approche va être O(N log N) .

• si vous utilisez le tri radix, qui se réduit à O(N) avec O(M) espace, où M est le nombre de caractères distincts dans le alphabet. (C'est-à 26 en anglais ... mais en théorie, nous devrions envisager multilingue anagrammes.)

• le "compte les caractères" en utilisant un tableau de comptes est aussi O(N) ... et plus rapide que le tri radix parce que vous n'avez pas besoin de reconstruire la chaîne triée. L'utilisation de l'espace sera O(M) .

• Une "de compter les caractères" à l'aide d'un dictionnaire, hashmap, treemap, ou équivalent sera plus lent que le tableau approche, à moins que l'alphabet soit énorme.

• l'élégante approche "produit-de-primes" est malheureusement O(N^2) dans le pire des cas, c'est parce que pour des mots ou des phrases assez longtemps, le produit des primes ne rentre pas dans un long . Cela signifie que vous devez utiliser BigInteger , et N fois la multiplication d'un BigInteger par une petite constante est O(N^2) .

  pour une hypothétique grand alphabet, le facteur d'échelle va être grand. Le pire cas d'utilisation de l'espace pour tenir le produit des nombres premiers comme un BigInteger est (je pense) O(N*logM) .

• a hashcode l'approche basée est habituellement O(N) si les mots ne sont pas des anagrammes. Si les hashcodes sont égaux, alors vous avez encore besoin de faire un test d'anagramme approprié. Ce n'est donc pas une solution complète.

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

public boolean isAnagram(String leftString, String rightString) {
  if (leftString == null || rightString == null) {
    return false;
  } else if (leftString.length() != rightString.length()) {
    return false;
  }

  Map<Character, Integer> 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 une solution moins générique mais un peu plus rapide. Vous devez placer votre alphabet ici:

public boolean isAnagram(String leftString, String rightString) {
  if (leftString == null || rightString == null) {
    return false;
  } else if (leftString.length() != rightString.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<Character, Integer> 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 sur deux cordes de longueur égale et suivons les différences entre elles. Nous ne nous soucions pas de ce que sont les différences, nous voulons juste savoir s'ils ont les mêmes caractères ou pas. Nous pouvons le faire en O (n/2) sans aucun traitement postérieur (ou beaucoup de nombres premiers).

public class TestAnagram {
  public static boolean isAnagram(String first, String second) {
    String positive = first.toLowerCase();
    String 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 string 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 de l'ASCII anglais de caractères jeu de caractères minuscules, mais il ne devrait pas être difficile à modifier à d'autres langues. Vous pouvez toujours utiliser une carte[caractère, Int] pour retrouver la même information, ce sera plus lent.

en utilisant plus de mémoire (une HashMap de au plus n/2 éléments)nous n'avons pas besoin de trier les chaînes.

public static boolean areAnagrams(String one, String two) {
    if (one.length() == two.length()) {
        String s0 = one.toLowerCase();
        String s1 = two.toLowerCase();
        HashMap<Character, Integer> chars = new HashMap<Character, Integer>(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 fait en cours d'exécution dans O(N) ... au lieu de O (NlogN) pour la solution qui trie les chaînes. Si je devais supposer que vous allez utiliser seulement des caractères alphabétiques, Je ne pourrais utiliser qu'un tableau de 26 ints (de A à z sans accents ou décorations) au lieu du hashmap.

si nous définissons que : N = |un| + |deux| nous faisons une itération sur N (Une fois sur un pour incrémenter les pions, et une fois pour les décrémenter sur deux). Ensuite, pour vérifier les totaux, nous itérons à mose N/2.

Les autres algorithmes décrits ont un avantage: ils n'utilisent pas de mémoire supplémentaire en supposant que les Tableaux.sort utilise les versions in place de quicksort ou de fusion sort. Mais puisque nous parlons d'anagrammes, je supposerai que nous parlons de langues humaines, donc les mots ne devraient pas être assez longs pour donner la mémoire. question.

    /*
 * 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(String[] args) {
        Anagrams an=new Anagrams();
        ArrayList<String> l=new ArrayList<String>();
        String result=JOptionPane.showInputDialog("How many words to test anagrams");
        if(Integer.parseInt(result) >1)
        {    
            for(int i=0;i<Integer.parseInt(result);i++)
            {

                String word=JOptionPane.showInputDialog("Enter word #"+i);
                l.add(word);   
            }
            System.out.println(an.isanagrams(l));
        }
        else
        {
            JOptionPane.showMessageDialog(null, "Can not be tested, \nYou can test two words or more");
        }

    }

    private static String sortString( String w )
    {
        char[] ch = w.toCharArray();
        Arrays.sort(ch);
        return new String(ch);
    }

    public boolean isanagrams(ArrayList<String> l)
    {
        boolean isanagrams=true; 
        ArrayList<String> anagrams = null;
        HashMap<String, ArrayList<String>> map =  new HashMap<String, ArrayList<String>>();
        for(int i=0;i<l.size();i++)
            {
        String word = l.get(i);
        String sortedWord = sortString(word);
            anagrams = map.get( sortedWord );
        if( anagrams == null ) anagrams = new ArrayList<String>();
        anagrams.add(word);
        map.put(sortedWord, anagrams);
            }

            for(int h=0;h<l.size();h++)
            {
                if(!anagrams.contains(l.get(h)))
                {
                    isanagrams=false;
                    break;
                }
            }

            return isanagrams;
        //}
        }

}

je suis un développeur C++ et le code ci-dessous est en C++. Je crois que la façon la plus rapide et la plus facile d'y aller serait la suivante:

crée un vecteur d'ints de taille 26, avec tous les slots initialisés à 0, et place chaque caractère de la chaîne dans la position appropriée dans le vecteur. Rappelez-vous, le vecteur est dans l'ordre alphabétique et donc si la première lettre dans la chaîne est z, il irait dans myvector[26]. Note: Ceci peut être fait en utilisant des caractères ASCII ainsi essentiellement, votre code ressemblera à quelque chose comme ceci:

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

ainsi, l'insertion de tous les éléments prendrait du temps O(n) car vous ne traverseriez la liste qu'une seule fois. Vous pouvez maintenant faire exactement la même chose pour la deuxième corde, et aussi prendre en O(n) fois. Vous pouvez ensuite comparer les deux vecteurs en vérifiant si les compteurs de chaque fente sont les mêmes. S'ils le sont, cela signifie que vous avez le même nombre de chaque caractère dans les deux cordes et donc ils sont anagrammes. Le la comparaison des deux vecteurs devrait également prendre du temps O (n) car vous ne le traversez qu'une fois.

Note: le code ne fonctionne que pour un seul mot de caractères. Si vous avez des espaces, des nombres et des symboles, vous pouvez juste créer un vecteur de taille 96 (caractères ASCII 32-127) et au lieu de dire - 'a' vous diriez - '' comme le caractère d'espace est le premier dans la liste ASCII de caractères.

j'espère que ça aidera. 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 le commentaire mentionnant la question " ac " - " bb "supposant a = 1 B=2 C=3, Nous pourrions simplement utiliser le carré de chaque entier qui représentent un char et résoudre le problème:

public boolean anagram(String s, String 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 souligné de faire des commentaires, tout en faisant des commentaires, j'ai trouvé qu'il y avait une logique incorrecte. J'ai corrigé la logique et ajouté des commentaires pour chaque morceau de code.

// Time complexity: O(N) where N is number of character in String
// Required space :constant space.
// will work for string that contains ASCII chars

private static boolean isAnagram(String s1, String s2) {

    // if length of both string'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 string 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 string 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.Faites d'abord exploser les chaînes en tableaux de caractères puis les trier et ensuite comparer 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(String s1, String s2) {

        StringBuilder sb1 = new StringBuilder();
        StringBuilder sb2 = new StringBuilder();
        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.toString());
        System.out.println(sb2.toString());

        if (sb1.toString().equals(sb2.toString()))
            return true;
        else
            return false;

    }

une réponse similaire peut avoir été postée en C++, la voici à nouveau en Java. Notez que la façon la plus élégante serait d'utiliser un tri pour stocker les caractères dans l'ordre trié, cependant, c'est une solution plus complexe. Une façon est d'utiliser un hashset pour stocker tous les mots que nous comparons et puis comparer un par un. Pour les comparer, faites un tableau de caractères avec l'index représentant la valeur ANCII des caractères (en utilisant un normalisateur depuis ie. Valeur ancienne de " a " est de 97) et le valeur représentant le nombre d'occurrences de ce caractère. Ceci s'exécute dans O(n) time et utilise O (m*z) space où m est la taille de currentWord et z la taille de storedWord, les deux pour lesquels nous créons un Char[].

public static boolean makeAnagram(String currentWord, String 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 distincts char , et non des points de code. Je voudrais proposer deux solutions pour bien gérer paires de substituts ainsi (ce sont les caractères de U+10000 à U+10FF , composé de deux char articles).

1) solution monoligne O(N logn) qui utilise Java 8 CharSequence.codePoints() stream:

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

2) moins élégant O (n) solution (en fait, il sera plus rapide que pour les longues cordes avec de faibles chances d'être anagrammes) :

static boolean areAnagrams(CharSequence a, CharSequence b) {
    int len = a.length();
    if (len != b.length())
        return false;

    // collect codepoint occurrences in "a"
    Map<Integer, Integer> 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 tout code :

1. La relation "sont des anagrammes" entre les cordes est un relation d'équivalence , afin de partitions de l'ensemble de toutes les chaînes dans des classes d'équivalence.
2. supposons que nous ayons une règle pour choisir un représentant (berceau) de chaque classe, alors il est facile de vérifier si deux classes sont les mêmes en comparant leurs représentants.
3. un représentant évident pour un ensemble de cordes est "le plus petit élément par ordre lexicographique ", qui est facile à calculer à partir de n'importe quel élément par Tri. Par exemple, le représentant de l'anagramme classe contenant "chapeau" est "aht'.

dans votre exemple" schoolmaster "et" theclassroom "sont des anagrammes parce qu'ils sont tous les deux dans la classe anagram avec berceau"acehlmoorsst".

en pseudo-code:

>>> 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(String args[]) {
        System.out.println(isAnagram(args[0].toUpperCase(),
                args[1].toUpperCase()));
    }
/**
 * 
 * @param word : The String 1
 * @param anagram_word : The String 2 with which Anagram to be verified
 * @return true or false based on Anagram
 */
    public static Boolean isAnagram(String word, String 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 String
        char[] anagram_word_char = anagram_word.toCharArray();//Get the Char Array of Second String
        int words_char_num = 1;//Initialize Multiplication Factor to 1
        int anagram_word_num = 1;//Initialize Multiplication Factor to 1 for String 2
        Map<Character, Integer> 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<Character, Integer> wordPrimeMap() {
        List<Integer> primes = primes(26);
        int k = 65;
        Map<Character, Integer> map = new TreeMap<Character, Integer>();
        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<Integer> primes(Integer N) {
        List<Integer> primes = new ArrayList<Integer>();
        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;
    }

}

IMHO, la solution la plus efficace a été fourni par @Siguza, Je l'ai étendu pour couvrir les cordes avec de l'espace E. g: "William Shakespeare"," I am a weakish speller"," School master"," the classroom "

public int getAnagramScore(String word, String anagram) {

        if (word == null || anagram == null) {
            throw new NullPointerException("Both, word and anagram, must be non-null");
        }

        char[] wordArray = word.trim().toLowerCase().toCharArray();
        char[] anagramArray = anagram.trim().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 triage.

public static boolean isAnagram(String s1, String s2){
    //case insensitive anagram

    StringBuffer sb = new StringBuffer(s2.toLowerCase());
    for (char c: s1.toLowerCase().toCharArray()){
        if (Character.isLetter(c)){

            int index = sb.indexOf(String.valueOf(c));
            if (index == -1){
                //char does not exist in other s2
                return false;
            }
            sb.deleteCharAt(index);
        }
    }
    for (char c: sb.toString().toCharArray()){
        //only allow whitespace as left overs
        if (!Character.isWhitespace(c)){
            return false;
        }
    }
    return true;
}

Tri approche n'est pas la meilleure. Il prend O(n) et O(nlogn). Au lieu de cela, faites une carte de hachage des caractères et comptez-les (les caractères d'incrément qui apparaissent dans la première chaîne et les caractères de décrément qui apparaissent dans la seconde chaîne). Quand un nombre atteint zéro, retirez-le du hash. Enfin, si deux chaînes sont des anagrammes, la table de hachage sera vide à la fin, sinon elle ne sera pas vide.

quelques notes importantes: (1) ignorer la lettre case et (2) ignorer l'espace blanc.

Voici l'analyse détaillée et la mise en œuvre en C#: test si deux chaînes sont des anagrammes

méthode simple pour déterminer si la corde d'essai est un Anagramme de la corde de base.

private static boolean isAnagram(String baseString, String testString){
    //Assume that there are no empty spaces in either string.

    if(baseString.length() != testString.length()){
        System.out.println("The 2 given words cannot be anagram since their lengths are different");
        return false;
    }
    else{
        if(baseString.length() == testString.length()){
            if(baseString.equalsIgnoreCase(testString)){
                System.out.println("The 2 given words are anagram since they are identical.");
                return true;
            }
            else{
                List<Character> 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 est assez intuitive. Une légère modification est nécessaire pour les mots avec un trait d'Union, mais pour les mots normaux, elle devrait fonctionner correctement.

    internal bool isAnagram(string input1,string input2)
    {
        Dictionary<char, int> 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<char, int> AddToDict(string input)
    {
        Dictionary<char, int> inputChars = new Dictionary<char, int>();
        foreach(char c in input)
        {
            if(inputChars.ContainsKey(c))
            {
                inputChars[c] += 1;
            }
            else
            {
                inputChars.Add(c, 1);
            }     
        }
        return inputChars;
    }

j'ai vu que personne n'a utilisé le "hashcode" approche pour trouver les anagrammes. J'ai trouvé mon approche peu différente que les approches discutées ci-dessus donc pensé à le partager. J'ai écrit le code ci-dessous pour trouver les anagrammes qui fonctionnent dans O(n).

/**
 * This class performs the logic of finding anagrams
 * @author ripudam
 *
 */
public class AnagramTest {

    public static boolean isAnagram(final String word1, final String 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 string received for anagram check to find the
         * hash
         */
        static class AnagramWrapper {
            String word;

            public AnagramWrapper(final String 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. Cependant, je suis en espérant que cela peut aider quelqu'un. La complexité temporelle de cette solution est O(N^2).

public boolean areAnagrams(final String word1, final String word2) {
        if (word1.length() != word2.length())
            return false;

        if (word1.equals(word2))
            return true;

        if (word1.length() == 0 && word2.length() == 0)
            return true;

        String 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;
}

Voici une autre approche utilisant HashMap en Java

public static boolean isAnagram(String first, String 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 String first, final String second) {
    Map<Character, Integer> counter = populateMap(first, second);
    return validateMap(counter);
}

private static boolean validateMap(Map<Character, Integer> counter) {
    for (int val : counter.values()) {
        if (val != 0) {
            return false;
        }
    }
    return true;
}

voici le cas d'essai

@Test
public void anagramTest() {
    assertTrue(StringUtil.isAnagram("keep" , "PeeK"));
    assertFalse(StringUtil.isAnagram("Hello", "hell"));
    assertTrue(StringUtil.isAnagram("SiLeNt caT", "LisTen cat"));       
}

private static boolean checkAnagram(String s1, String 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;
}

vous devriez utiliser quelque chose comme ça:

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

valeur par défaut pour isFound devrait être false. Juste

une façon de résoudre ce problème - basée sur la réponse de Sai Kiran..

import java.util.Scanner;

public class Anagram {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        System.out.print("Enter first word : ");
        String word1 = sc.nextLine();
        System.out.print("Enter second word : ");
        String word2 = sc.nextLine();

        sc.close();

        System.out.println("Is Anagram : " + isAnagram(word1, word2));
    }

    private static boolean isAnagram(String word1, String 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, i.e., words having same characters but with different counts!");
            return false;
        }

        return true;
    }
}

fonctionne parfaitement! Mais ce n'est pas une bonne approche parce Qu'elle fonctionne en O(N^2)

boolean isAnagram(String A, String 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;
}

j'avais écrit ce programme en java. Je pense que cela pourrait aussi aider:

public class Anagram {
    public static void main(String[] args) {
        checkAnagram("listen", "silent");
    }

    public static void checkAnagram(String str1, String str2) {
        boolean isAnagram = false;
        str1 = sortStr(str1);
        str2 = sortStr(str2);
        if (str1.equals(str2)) {
            isAnagram = true;
        }
        if (isAnagram) {
            System.out.println("Two strings are anagram");
        } else {
            System.out.println("Two string are not anagram");
        }

    }

    public static String sortStr(String 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;
                }
            }
        }
        String output = String.valueOf(strArr);
        return output;
    }
}