Was ist eine einfache Art zu sagen, ob eine Liste von Wörtern Anagramme von einander sind?

Question

Wie würden Sie Wörter auflisten, die Anagramme von einander sind?

Ich wurde diese Frage gestellt, als ich mich für meinen aktuellen Job bewarb.

orchestra kann in carthorse umgeordnet werden mit allen ursprünglichen Buchstaben verwendet genau einmal deshalb sind die Wörter Anagramme von einander.

Answer 1

Geben Sie alle Buchstaben in alphabetischer Reihenfolge in die Zeichenfolge ein (Sortieralgorithmus) und vergleichen Sie dann die resultierende Zeichenfolge.

-Adam

Answer 2

Sortierung jedes Element (Entfernen von Leerzeichen) und Vergleich mit dem vorherigen. Wenn sie alle gleich sind, sind sie alle Anagramme.

Answer 3

sortieren Briefe und vergleichen (Buchstaben für Buchstaben, string vergleichen, ...) ist das erste, was in den Sinn kommt.

Answer 4

sollte Der folgende Algorithmus arbeiten:

1. Sortieren Sie die Buchstaben in jedem Wort.

2. Sortieren Sie die sortierten Listen von Buchstaben in jeder Liste.

3. Vergleichen Sie jedes Element in jeder Liste auf Gleichheit.

Answer 5

Interessanterweise Eric Lippert's Fabulous Adventures In Coding Blog mit einer Variation dieses sehr Problem am 4. Februar behandeln 2009 in this post.

Answer 6

Gut, dass wir alle in der C# -Realität der In-Place-Sortierung von kurzen Wörtern auf Quad-Core-Maschinen mit oozles Speicher leben. :-)

Wenn Sie jedoch Speicher beschränkt sind und die Originaldaten nicht berühren können und Sie wissen, dass diese Wörter Zeichen aus der unteren Hälfte der ASCII-Tabelle enthalten, können Sie einen anderen Algorithmus verwenden, der zählt das Auftreten jedes Buchstabens in jedem Wort anstelle des Sortierens.

Sie könnten sich auch für diesen Algorithmus entscheiden, wenn Sie es in O (N) machen wollen und sich nicht um die Speichernutzung kümmern (ein Zähler für jedes Unicode-Zeichen kann ziemlich teuer sein).

Answer 7

1. vergleichen Länge (wenn nicht gleich, keine Chance)
2. machen einen Bitvektor der Länge der Saiten
3. für jede char in der ersten Zeichenfolge Vorkommen es in der zweiten
4. finden das Bit für das erste ungesetzt Auftreten
5. , wenn Sie eine Station mit fehler
finden

Answer 8

Nun die Worte in der Liste sortieren.

Wenn abc, bca, cab, cba die Eingänge sind, dann wird die sortierte Liste abc, abc, abc, abc sein.

Jetzt sind alle ihre Hash-Codes gleich.Vergleichen Sie die HashCodes.

Answer 9

public static void main(String[] args) { 

    String s= "abc"; 
    String s1="cba"; 



    char[] aArr = s.toLowerCase().toCharArray(); 
    char[] bArr = s1.toLowerCase().toCharArray(); 

    // An array to hold the number of occurrences of each character 
    int[] counts = new int[26]; 

    for (int i = 0; i < aArr.length; i++){ 
    counts[aArr[i]-97]++; // Increment the count of the character at respective position 
    counts[bArr[i]-97]--; // Decrement the count of the character at respective position 
    } 

    // If the strings are anagrams, then counts array will be full of zeros not otherwise 
    for (int i = 0; i<26; i++){ 
    if (counts[i] != 0) 
    return false; 
    } 

Answer 10

Versuchte hashcode Logik für Anagramm mich falsch Ausgang

public static Boolean anagramLogic(String s,String s2){ 
    char[] ch1 = s.toLowerCase().toCharArray(); 
     Arrays.sort(ch1); 
     char[] ch2= s2.toLowerCase().toCharArray(); 
     Arrays.sort(ch2); 
     return ch1.toString().hashCode()==ch2.toString().hashCode(); //wrong 
    } 

, um diesen Code zu korrigieren, ist die einzige Option unten gibt, gebe ich zu sehen, zu schätzen wissen alle Empfehlungen

char[] ch1 = s.toLowerCase().toCharArray(); 
     Arrays.sort(ch1); 
     char[] ch2= s2.toLowerCase().toCharArray(); 
     Arrays.sort(ch2); 
     return Arrays.equals(ch1,ch2); 
    }