Beste Lösung für einen Anagramm-Check?

Question

Ich gehe durch ein Permutations-/Anagramm-Problem und wollte Eingabe auf die effizienteste Art der Überprüfung. Jetzt mache ich das in Java Land, und als solche gibt es eine Bibliothek für alles inklusive Sortieren. Das erste Mittel, um zu überprüfen, ob zwei Strings Anagramme von einander sind, besteht darin, die Länge zu prüfen, sie auf irgendeine Weise zu sortieren und dann jeden Index der Zeichenkette zu vergleichen. Code unten:

private boolean validAnagram(String str, String pair) { 
if(str.length() != pair.length()){ 
    return false; 
} 

char[] strArr = str.toCharArray(); 
char[] pairArr = pair.toCharArray(); 


Arrays.sort(strArr); 
str = new String(strArr); 

Arrays.sort(pairArr); 
pair = new String(pairArr); 

for(int i = 0; i<str.length(); i++){ 
    if(str.charAt(i) != pair.charAt(i)){ 
     return false; 
    } 
} 
return true; 
} 

Alternativ dachte ich, es wäre einfacher, eine Kontrolle über alle möglichen Zeichen zu überprüfen, basierend auf ASCII-Wert und vermeiden. Code unten:

private boolean validAnagram(String str, String pair) { 
if(str.length() != pair.length()){ 
    return false; 
} 

char[] strArr = str.toCharArray(); 
char[] pairArr = pair.toCharArray(); 



int strValue = 0; 
int pairValue = 0; 

for(int i =0; i < strArr.length; i++){ 
    strValue+= (int) strArr[i]; 
    pairValue+= (int) pairArr[i]; 
} 

if(strValue != pairValue){ 
    return false; 
} 
return true; 
} 

Also, was ist eine bessere Lösung? Ich weiß nicht viel über die Art, die mir Arrays zur Verfügung stellen, aber das ist die häufigere Antwort, wenn ich mich in den alten Netzen umschaue. Ich frage mich, ob ich etwas verpasse.

Answer 1

Es gibt mehrere Möglichkeiten zu überprüfen, ob zwei Strings Anagramme sind oder nicht. Ihre Frage ist, welche ist eine bessere Lösung. Ihre erste Lösung hat Sortierlogik. Sortierung hat Worst-Case-Komplexität von (nlogn). Ihre zweite Logik verwendet nur eine Schleife mit der Komplexität O (n).

Aus diesen zwei, Ihre zweite Lösung, die nur O (n) Komplexität hat, wird eine bessere Lösung als die erste sein.

Eine mögliche Lösung:

private boolean checkAnagram(String stringOne , String stringTwo){ 
     char[] first = stringOne.toLowerCase().toCharArray(); 
     char[] second = stringTwo.toLowerCase().toCharArray(); 
     // if length of strings is not same 
     if (first.length != second.length) 
      return false; 
     int[] counts = new int[26]; 
     for (int i = 0; i < first.length; i++){ 
      counts[first[i]-97]++; 
      counts[second[i]-97]--; 
     } 
     for (int i = 0; i<26; i++) 
      if (counts[i] != 0) 
       return false; 
     return true; 
    } 

Answer 2

Die beste Lösung ist abhängig von Ihrem Ziel, Codegröße, Speicherbedarf oder am wenigsten Berechnung.

Eine sehr coole Lösung, weniger Code wie möglich, nicht der schnellste O (n log n) sein und ziemlich Speicher ineffizient in Java 8:

public class Anagram { 
    public static void main(String[] argc) { 
    String str1 = "gody"; 
    String str2 = "dogy"; 

    boolean isAnagram = 
    str1.chars().mapToObj(c -> (char) c).sorted().collect(Collectors.toList()) 
    .equals(str2.chars().mapToObj(c -> (char) c).sorted().collect(Collectors.toList())); 

    System.out.println(isAnagram); 
    } 
} 

Answer 3

habe ich versucht, ein paar Lösungen Sets mit und machte jeden laufen 10 Millionen mal testen Sie Ihr Beispiel Array verwenden:

private static String[] input = {"tea", "ate", "eat", "apple", "java", "vaja", "cut", "utc"};

Erstens i die verwendete Methode nennen diese algotirhms:

public static void main(String[] args) { 
    long startTime = System.currentTimeMillis(); 
    for (int x = 0; x < 10000000; x++) { 
     Set<String> confirmedAnagrams = new HashSet<>(); 
     for (int i = 0; i < (input.length/2) + 1; i++) { 
      if (!confirmedAnagrams.contains(input[i])) { 
       for (int j = i + 1; j < input.length; j++) { 
         if (isAnagrams1(input[i], input[j])) { 
          confirmedAnagrams.add(input[i]); 
          confirmedAnagrams.add(input[j]); 
         } 
       } 
      } 
     } 
     output = confirmedAnagrams.toArray(new String[confirmedAnagrams.size()]); 
    } 
    long endTime = System.currentTimeMillis(); 
    System.out.println("Total time: " + (endTime - startTime)); 
    System.out.println("Average time: " + ((endTime - startTime)/10000000D)); 
} 

Ich habe dann Algorithmen basierend auf einem HashSet von Zeichen verwendet. Ich füge jedes Zeichen jedes Wortes zum HashSet hinzu, und sollte das HashSet nicht die Länge der Initialwörter sein, würde es bedeuten, dass es sich nicht um Anagramme handelt.

Meine Algorithmen und deren Laufzeiten:

Algorithmus 1:

private static boolean isAnagrams1(String x, String y) { 
    if (x.length() != y.length()) { 
     return false; 
    } else if (x.equals(y)) { 
     return true; 
    } 

    Set<Character> anagramSet = new HashSet<>(); 
    for (int i = 0; i < x.length(); i++) { 
     anagramSet.add(x.charAt(i)); 
     anagramSet.add(y.charAt(i)); 
    } 

    return anagramSet.size() != x.length(); 
} 

Dies hat die Laufzeit:

Total time: 6914 
Average time: 6.914E-4 

Algorithmus 2

private static boolean isAnagrams2(String x, String y) { 
    if (x.length() != y.length()) { 
     return false; 
    } else if (x.equals(y)) { 
     return true; 
    } 

    Set<Character> anagramSet = new HashSet<>(); 
    char[] xAr = x.toCharArray(); 
    char[] yAr = y.toCharArray(); 
    for (int i = 0; i < xAr.length; i++) { 
     anagramSet.add(xAr[i]); 
     anagramSet.add(yAr[i]); 
    } 

    return anagramSet.size() != x.length(); 
} 

hat die Laufzeit von:

Total time: 8752 
Average time: 8.752E-4 

Algorithmus 3

Für diesen Algorithmus, entschied ich mich durch das Set zu schicken, also einmal für jeden Zyklus, ich es nur schaffen und es nach jedem löschen Prüfung.

private static boolean isAnagrams3(Set<Character> anagramSet, String x, String y) { 
    if (x.length() != y.length()) { 
     return false; 
    } else if (x.equals(y)) { 
     return true; 
    } 

    for (int i = 0; i < x.length(); i++) { 
     anagramSet.add(x.charAt(i)); 
     anagramSet.add(y.charAt(i)); 
    } 

    return anagramSet.size() != x.length(); 
} 

hat die Laufzeit von:

Total time: 8251 
Average time: 8.251E-4 

Algorithmus 4

Dieser Algorithmus ist nicht mein, gehört es zu Pratik Upacharya die auch die Frage beantwortet, für mich, um zu vergleichen :

private static boolean isAnagrams4(String stringOne, String stringTwo) { 
    char[] first = stringOne.toLowerCase().toCharArray(); 
    char[] second = stringTwo.toLowerCase().toCharArray(); 
    // if length of strings is not same 
    if (first.length != second.length) { 
     return false; 
    } 
    int[] counts = new int[26]; 
    for (int i = 0; i < first.length; i++) { 
     counts[first[i] - 97]++; 
     counts[second[i] - 97]--; 
    } 
    for (int i = 0; i < 26; i++) { 
     if (counts[i] != 0) { 
      return false; 
     } 
    } 
    return true; 
} 

Hat t er Laufzeit:

Total time: 5707 
Average time: 5.707E-4 

Natürlich ist diese Laufzeiten für jeden Testlauf unterscheiden, und um einen ordnungsgemäße Prüfung zu tun, ein größerer Beispielsatz benötigt wird, und vielleicht mehr Iterationen davon.

* Herausgegeben, wie ich einen Fehler in meinen ersten Verfahren hergestellt, ist Pratik Upacharya's Algorithmus scheint eine sehr einfache Implementierung die schnellere

Answer 4

hier zu sein.

public boolean isAnagram(String strA, String strB) { 
    // Cleaning the strings (remove white spaces and convert to lowercase) 
    strA = strA.replaceAll("\\s+","").toLowerCase(); 
    strB = strB.replaceAll("\\s+","").toLowerCase(); 

    // Check every char of strA and removes first occurence of it in strB 
    for (int i = 0; i < strA.length(); i++) { 
    if (strB.equals("")) return false; // strB is already empty : not an anagram 
    strB = strB.replaceFirst(Pattern.quote("" + strA.charAt(i)), ""); 
    } 

    // if strB is empty we have an anagram 
    return strB.equals(""); 
} 

Und schließlich:

System.out.println(isAnagram("William Shakespeare", "I am a weakish speller")); // true 

Answer 5

//here best solution for an anagram 
import java.util.*; 

class Anagram{ 
public static void main(String arg[]){ 

Scanner sc =new Scanner(System.in); 
String str1=sc.nextLine(); 
String str2=sc.nextLine(); 
int i,j; 

boolean Flag=true; 
i=str1.length(); 
j=str2.length(); 


if(i==j){ 
for(int m=0;m<i;m++){ 
    for(int n=0;n<i;n++){ 
     if(str1.charAt(m)==str2.charAt(n)){ 
      Flag=true; 
      break; 
      } 
      else 
      Flag=false; 
    } 
} 
} 
else{ 
Flag=false; 
} 

if(Flag) 
System.out.println("String is Anagram"); 
else 
System.out.println("String is not Anagram"); 
} 
} 

Answer 6

Ein Werber hat mich gebeten, dieses Problem vor kurzem zu lösen. Bei der Untersuchung des Problems kam ich mit einer Lösung, die zwei Typen Anagramm Probleme löst.

Problem 1: Bestimmen Sie, ob ein Anagramm in einem Textkörper existiert.

Problem 2: Bestimmen Sie, ob ein formelles Anagramm in einem Textkörper vorhanden ist. In diesem Fall muss das Anagramm die gleiche Größe haben wie der Text , mit dem es verglichen wird. Im ersten Fall müssen die beiden Texte nicht die gleiche Größe haben.
Man muss nur das andere enthalten.

war mein Ansatz wie folgt:

Aufbauphase: Zuerst ein Anagramm Klasse erstellen. Dies wird nur den Text in eine Map konvertieren, deren Schlüssel das betreffende Zeichen enthält und der Wert die Nummer des Auftretens des Eingabezeichens enthält. Ich nehme an, dass dies höchstens O (n) Zeit Komplexität erfordern würde. Und da dies höchstens zwei Karten erfordern würde, wäre die Worst-Case-Komplexität O (2n). Zumindest mein naives Verständnis der asymptotischen Notationen sagt das.

Verarbeitungsphase: Alles, was Sie tun müssen, ist Schleife durch die kleinere der beiden Karten und suchen Sie es in der größeren Karte. Wenn es nicht existiert oder wenn es existiert , aber mit einer anderen Anzahl von Vorkommen, es fehlschlägt der Test ein Anagramm zu sein.

Hier ist die Schleife, die, wenn wir ein Anagramm oder nicht haben bestimmt:

boolean looking = true; 
     for (Anagram ele : smaller.values()) { 
      Anagram you = larger.get(ele); 
       if (you == null || you.getCount() != ele.getCount()) { 
        looking = false; 
        break; 
       } 
     } 
     return looking; 

Bitte beachte, dass ich eine ADT die Strings verarbeitet werden enthalten. Sie werden zuerst in eine Karte konvertiert.

Hier ein Ausschnitt des Codes ist das Anagramm Objekt zu erstellen:

private void init(String teststring2) { 
     StringBuilder sb = new StringBuilder(teststring2); 
     for (int i = 0; i &lt sb.length(); i++) { 
      Anagram a = new AnagramImpl(sb.charAt(i)); 
      Anagram tmp = map.putIfAbsent(a, a); 
      if (tmp != null) { 
       tmp.updateCount(); 
      } 
     } 
    }