So prüfen Sie, ob zwei Wörter Anagramme sind

Zwei Wörter sind Diagramme voneinander, wenn sie dieselbe Anzahl von Zeichen und dieselben Zeichen enthalten. Sie müssen nur die Zeichen in lexikographischer Reihenfolge sortieren und bestimmen, ob alle Zeichen in einer Zeichenfolge und in derselben Reihenfolge wie alle Zeichen in der anderen Zeichenfolge sind.

Hier ist ein Codebeispiel. Sehen Sie sich die API unter Arrays an, um zu verstehen, was hier vor sich geht.

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

Wenn Sie eines der Arrays sortieren, wird die Lösung zu O (n log n). Wenn Sie jedoch eine Hashmap verwenden, ist dies O (n). getestet und funktioniert.

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;

Hier ist eine einfache schnelle O(n) - Lösung, ohne Sortierungen oder mehrere Schleifen oder Hash-Maps zu verwenden. Wir erhöhen den Zählwert jedes Zeichens im ersten Array und dekrementieren den Zählwert jedes Zeichens im zweiten Array. Wenn das resultierende Anzahlenfeld voller Nullen ist, sind die Zeichenfolgen Anagramme. Kann erweitert werden, um andere Zeichen einzuschließen, indem das Zählungsfeld vergrößert wird.

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]));
    }
}

Viele Leute haben Lösungen vorgestellt, aber ich möchte nur über die algorithmische Komplexität einiger der gängigen Ansätze sprechen:

• Die einfache Methode zum Sortieren der Zeichen mit Arrays.sort() lautet O(N log N).

• Wenn Sie die Radix-Sortierung verwenden, reduziert sich dies auf O(N) mit O(M) space, wobei M die Anzahl der verschiedenen Zeichen im Alphabet ist. (Das sind 26 auf Englisch ... aber theoretisch sollten wir mehrsprachige Anagramme berücksichtigen.)

• Das "Zählen der Zeichen" mit einem Array von Zählungen ist ebenfalls O(N) ... und schneller als das Sortieren nach Radix, da der sortierte String nicht rekonstruiert werden muss. Die Speicherplatznutzung wird O(M) sein.

• Ein "Zählen der Zeichen" unter Verwendung eines Wörterbuchs, einer Hashmap, einer Baumkarte oder eines entsprechenden Objekts ist langsamer als das Array, wenn das Alphabet nicht sehr groß ist.

• Der elegante Ansatz des "Produkt der Primzahlen" ist im schlimmsten Fall leider O(N^2). Dies liegt daran, dass bei lang genug Wörtern oder Ausdrücken das Produkt der Primzahlen nicht in eine long passt. Das bedeutet, dass Sie BigInteger verwenden müssen, und N-mal eine BigInteger multipliziert mit einer kleinen Konstanten ist O(N^2). 

  Für ein hypothetisches großes Alphabet wird der Skalierungsfaktor groß sein. Die Verwendung des Produkts der Primzahlen im schlimmsten Fall als BigInteger ist (denke ich) O(N*logM).

• Ein auf hashcode basierender Ansatz ist normalerweise O(N), wenn die Wörter keine Anagramme sind. Wenn die Hashcodes gleich sind, müssen Sie dennoch einen ordnungsgemäßen Anagrammtest durchführen. Dies ist also keine vollständige Lösung.

O (n) -Lösung ohne Sortierung und Verwendung nur einer Karte. 

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

und weniger generische Lösung, aber etwas schneller. Sie müssen Ihr Alphabet hier platzieren:

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

Wir laufen zwei gleich lange Saiten und verfolgen die Unterschiede zwischen ihnen. Uns ist es egal, was die Unterschiede sind, wir möchten nur wissen, ob sie die gleichen Charaktere haben oder nicht. Dies ist in O(n/2) ohne Nachbearbeitung (oder viele Primzahlen) möglich.

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

Ja, dieser Code ist vom englischen Zeichensatz ASCII mit Kleinbuchstaben abhängig, es sollte jedoch nicht schwierig sein, ihn in andere Sprachen zu ändern. Sie können immer eine Karte [Character, Int] verwenden, um die gleichen Informationen zu verfolgen. Dies ist nur langsamer.

Viele komplizierte Antworten hier. Basierend auf der akzeptierten Antwort und dem Kommentar , der die 'ac' - 'bb'-Ausgabe erwähnt, unter der Annahme, dass A = 1 B = 2 C = 3 ist, könnten wir einfach das Quadrat jeder Ganzzahl verwenden, die ein Zeichen darstellt und löse das Problem:

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

    /*
 * 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;
        //}
        }

}

Durch die Verwendung von mehr Arbeitsspeicher (einer HashMap mit höchstens N/2 Elementen) müssen wir die Zeichenfolgen nicht sortieren.

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

Diese Funktion wird tatsächlich in O(N) ... anstelle von O(NlogN) für die Lösung ausgeführt, die die Zeichenfolgen sortiert. Wenn ich davon ausgehen würde, dass Sie nur alphabetische Zeichen verwenden, könnte ich anstelle der Hashmap nur ein Array von 26 Ints (von a bis z ohne Akzente oder Dekorationen) verwenden.

Wenn wir das definieren: N = | one | + | two | Wir führen eine Iteration über N durch (einmal über eins, um die Zähler zu erhöhen, und einmal, um sie um zwei zu erniedrigen).

Die anderen beschriebenen Algorithmen haben einen Vorteil: Sie verwenden keinen zusätzlichen Speicher, vorausgesetzt Arrays.sort verwendet Inplace-Versionen von QuickSort oder die Zusammenführungssortierung. Da wir jedoch über Anagramme sprechen, gehe ich davon aus, dass wir über menschliche Sprachen sprechen. Daher sollten Wörter nicht lang genug sein, um Gedächtnisprobleme zu erzeugen.

Ich bin ein C++ - Entwickler und der folgende Code ist in C++. Ich glaube, der schnellste und einfachste Weg, dies zu tun, wäre folgender:

Erstellen Sie einen Vektor aus Zentimetern der Größe 26, wobei alle Slots auf 0 initialisiert sind, und platzieren Sie jedes Zeichen der Zeichenfolge an der entsprechenden Stelle im Vektor. Denken Sie daran, dass der Vektor in alphabetischer Reihenfolge ist. Wenn also der erste Buchstabe in der Zeichenfolge z ist, würde er in myvector gehen [26]. Hinweis: Dies kann mit ASCII Zeichen erfolgen, so dass Ihr Code im Wesentlichen so aussieht:

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

Das Einfügen aller Elemente würde O(n) Zeit in Anspruch nehmen, da Sie die Liste nur einmal durchlaufen würden. Sie können jetzt genau dasselbe für die zweite Saite tun, und dies würde O(n) Zeit in Anspruch nehmen. Sie können die beiden Vektoren dann vergleichen, indem Sie prüfen, ob die Zähler in jedem Slot gleich sind. Wenn dies der Fall ist, bedeutet dies, dass Sie in beiden Zeichenfolgen die gleiche Anzahl JEDER Zeichen und somit Anagramme hatten. Der Vergleich der beiden Vektoren sollte auch O(n) Zeit in Anspruch nehmen, da Sie sie nur einmal durchlaufen. 

Hinweis: Der Code funktioniert nur für ein einzelnes Word-Zeichen. Wenn Sie Leerzeichen sowie Zahlen und Symbole haben, können Sie einfach einen Vektor der Größe 96 (ASCII-Zeichen 32-127) erstellen ASCII Liste der Zeichen.

Ich hoffe das hilft. Wenn ich irgendwo einen Fehler gemacht habe, bitte einen Kommentar hinterlassen.

Danke, dass Sie darauf hingewiesen haben, einen Kommentar abzugeben. Während ich den Kommentar machte, stellte ich fest, dass eine falsche Logik vorlag. Ich habe die Logik korrigiert und für jeden Code einen Kommentar hinzugefügt.

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

Bislang arbeiten alle vorgeschlagenen Lösungen mit separaten char-Elementen, nicht mit Code-Punkten. Ich möchte zwei Lösungen vorschlagen, um Surrogat-Paare richtig zu behandeln (dies sind Zeichen von U + 10000 bis U + 10FFFF , die aus zwei char-Elementen bestehen).

1) Einzeilige O (n logn) - Lösung, die Java 8 CharSequence.codePoints() stream verwendet:

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

2) Weniger elegant O(n) Lösung (Tatsächlich ist es nur für lange Strings mit geringen Chancen, Anagramme zu sein):

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

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, die effizienteste Lösung wurde von @Siguza bereitgestellt. Ich habe sie erweitert, um Strings mit Leerzeichen abzudecken, z.

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();

    }

Wie ein Mathematiker über das Problem denken könnte , bevor er Code schreibt :

1. Die Beziehung "sind Anagramme" zwischen Zeichenfolgen ist eine Äquivalenzrelation, also unterteilt sie die Menge aller Zeichenfolgen in Äquivalenzklassen.
2. Angenommen, wir hatten die Regel, aus jeder Klasse ein Vertreter (Kinderbett) zu wählen, dann ist es einfach zu testen, ob zwei Klassen gleich sind, indem ihre Vertreter verglichen werden.
3. Ein offensichtlicher Vertreter für eine Reihe von Zeichenfolgen ist "das kleinste Element in lexikografischer Reihenfolge", das durch Sortieren aus jedem Element leicht berechnet werden kann. Beispielsweise ist der Vertreter der Anagrammklasse, die 'hat' enthält, 'aht'.

In Ihrem Beispiel sind "Schulmeister" und "Klassenzimmer" Anagramme, da sie beide in der Anagrammklasse mit der Krippe "acehlmoorsst" sind.

Im Pseudocode:

>>> def crib(Word):
...     return sorted(Word)
...
>>> crib("schoolmaster") == crib("theclassroom")
True

Hier ist meine Lösung. Explodieren Sie zuerst die Zeichenketten in Char-Arrays, sortieren Sie sie und vergleichen Sie, ob sie gleich sind oder nicht. Ich denke, die Komplexität dieses Codes ist O (a + b). Wenn a = b, können wir O (2A) sagen.

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;

    }

Eine ähnliche Antwort wurde möglicherweise in C++ gepostet, hier ist es wieder in Java. Beachten Sie, dass die eleganteste Methode die Verwendung der Trie ist, um die Zeichen in sortierter Reihenfolge zu speichern. Dies ist jedoch eine komplexere Lösung. Eine Möglichkeit ist, ein Hash-Set zu verwenden, um alle Wörter, die wir vergleichen, zu speichern und sie dann einzeln zu vergleichen. Um sie zu vergleichen, erstellen Sie ein Array von Zeichen mit dem Index, der den ANCII-Wert der Zeichen darstellt (unter Verwendung eines Normalizers, da der ANCII-Wert von 'a' 97 ist) und den Wert, der die Anzahl der Vorkommen dieses Zeichens darstellt. Dies wird in der Zeit O(n) ausgeführt und verwendet den O (m * z) -Raum, wobei m die Größe des aktuellenWords und z die Größe des gespeichertenWords ist, für die wir ein Char [] erstellen.

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

Der Sortieransatz ist nicht der beste. Es braucht O(n) Platz und O(nlogn) Zeit. Erstellen Sie stattdessen eine Hash-Map aus Zeichen und zählen Sie sie (erhöhen Sie die Zeichen, die in der ersten Zeichenfolge enthalten sind, und verringern Sie die Zeichen, die in der zweiten Zeichenfolge erscheinen). Wenn eine bestimmte Anzahl Null erreicht, entfernen Sie sie aus dem Hash. Wenn zwei Zeichenfolgen Anagramme sind, ist die Hash-Tabelle am Ende leer - ansonsten ist sie nicht leer.

Einige wichtige Hinweise: (1) Groß-/Kleinschreibung ignorieren und (2) Leerzeichen ignorieren.

Hier ist die detaillierte Analyse und Implementierung in C #: Testen, ob zwei Zeichenketten Anagramme sind

Hier ist ein anderer Ansatz, der HashMap in Java verwendet

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

Hier ist der Testfall

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

// When this method returns 0 means strings are Anagram, else Not.

public static int isAnagram(String str1, String str2) {
        int value = 0;
        if (str1.length() == str2.length()) {
            for (int i = 0; i < str1.length(); i++) {
                value = value + str1.charAt(i);
                value = value - str2.charAt(i);
            }

        } else {
            value = -1;
        }
        return value;
    }

Die einfachste Lösung mit Komplexität O(N) verwendet Map.

public static Boolean checkAnagram(String string1, String string2) {
    Boolean anagram = true;

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


    char[] chars1 = string1.toCharArray();
    char[] chars2 = string2.toCharArray();

    for(int i=0; i<chars1.length; i++) {
        if(map1.get(chars1[i]) == null) {
            map1.put(chars1[i], 1);
        } else {
            map1.put(chars1[i], map1.get(chars1[i])+1);
        }

        if(map2.get(chars2[i]) == null) {
            map2.put(chars2[i], 1);
        } else {
            map2.put(chars2[i], map2.get(chars2[i])+1);
        }
    }

    Set<Map.Entry<Character, Integer>> entrySet1 = map1.entrySet();
    Set<Map.Entry<Character, Integer>> entrySet2 = map2.entrySet();
    for(Map.Entry<Character, Integer> entry:entrySet1) {

        if(entry.getValue() != map2.get(entry.getKey())) {
            anagram = false;
            break;
        }
    }

    return anagram;
}

Ich habe gesehen, dass niemand den "Hashcode" -Ansatz verwendet hat, um die Anagramme herauszufinden. Ich fand meinen Ansatz etwas anders als die oben diskutierten Ansätze und dachte daher daran, ihn zu teilen. Ich habe den folgenden Code geschrieben, um die Anagramme zu finden, die in O (n) funktionieren. 

/**
 * 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;
            }
         }
    }

Eine einfache Methode, um herauszufinden, ob der testString ein Anagramm des baseString ist.

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

Entschuldigung, die Lösung ist in C #, aber ich denke, die verschiedenen Elemente, mit denen die Lösung gefunden wird, sind ziemlich intuitiv. Ein leichter Tweak ist für Wörter mit Bindestrich erforderlich, aber für normale Wörter sollte es gut funktionieren.

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

Eine andere Lösung ohne zu sortieren.

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

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