Anagramm-Algorithmus mit minimaler Komplexität

Question

Vor kurzem wurde ich gebeten, einen Algorithmus zu entwickeln, der prüft, ob zwei Zeichenketten Anagramme voneinander sind. Mein Ziel war es, die Raum- und Zeitkomplexität zu minimieren, also habe ich mir diesen Algorithmus ausgedacht:

1. Erstellen Sie ein Array mit 26 Elementen, die jeweils mit Null initialisiert werden.
2. Durchlaufen Sie die erste Zeichenkette und erhöhen Sie für jedes Zeichen das Array-Element, das diesem Zeichen entspricht.
3. Durchlaufen Sie die zweite Zeichenkette und dekrementieren Sie für jedes Zeichen das Array-Element, das diesem Zeichen entspricht.
4. Scannen Sie das Feld. Wenn alle Elemente 0 sind, sind die beiden Zeichenketten Anagramme.

Die Zeitkomplexität dieses Algorithmus ist jedoch O(n) und ich kann keinen Algorithmus mit geringerer Komplexität finden. Kennt jemand einen solchen?

Answer 1

Ihr Algorithmus ist asymptotisch optimal. Es ist nicht möglich, dieses Problem in mehr als Ω(n)-Zeit zu lösen. Um dies zu sehen, nehmen wir an, dass es einen Algorithmus A gibt, der das Problem in o(n) Zeit lösen kann (beachten Sie, dass dies hier little-o von n ist). Dann gibt es für jedes 1 > ε > 0 ein solches n, dass der Algorithmus für jede Eingabe der Größe mindestens n in höchstens εn Schritten beendet sein muss. Setzen Sie ε = 1/3 und betrachten Sie alle Eingaben für den Algorithmus, die mindestens die Länge n für das oben genannte n für dieses ε haben. Da der Algorithmus höchstens 1/3 der Zeichen in den beiden Zeichenketten betrachten kann, muss es zwei verschiedene Eingaben für die Funktion geben, eine, die ein Paar von Anagrammen ist, und eine, die kein Paar ist, so dass der Algorithmus dieselbe Teilmenge der Zeichen jeder Eingabe betrachtet. Die Funktion müsste dann in jedem Fall die gleiche Ausgabe produzieren und wäre somit bei mindestens einer der Eingaben falsch. Wir haben einen Widerspruch erreicht, also kann es keinen solchen Algorithmus geben.

Answer 2

Möglicherweise können Sie die durchschnittliche Leistung durch frühzeitige Ausstiege verbessern. Wenn beim Scannen der 2. Zeichenkette count[char] vor dem Dekrementieren 0 ist, liegt kein Anagramm vor und Sie können das Scannen beenden.

Wenn die Zeichenfolgen kürzer als 26 Zeichen sind, werden im letzten Schritt nur die Zeichen der ersten Zeichenfolge auf Nullen geprüft.

Das ändert nichts am großen O, aber es kann Ihre durchschnittliche Laufzeit auf etwas weniger als die 2N+26 der vorgeschlagenen Lösung ändern, abhängig von Ihren Daten.

Answer 3

Stellen wir eine Frage: Schreiben Sie eine Funktion, die feststellt, ob t ein Anagramm von s ist, wenn zwei Zeichenketten s und t gegeben sind.

Zum Beispiel: s = "anagram", t = "nagaram", return true. s = "rat", t = "car", return false.

Methode 1 (HashMap verwenden):

    public class Method1 {

    public static void main(String[] args) {
        String a = "protijayi";
        String b = "jayiproti";
        System.out.println(isAnagram(a, b ));// output => true

    }

    private static boolean isAnagram(String a, String b) {
        Map<Character ,Integer> map = new HashMap<>();
        for( char c : a.toCharArray()) {
            map.put(c,    map.getOrDefault(c, 0 ) + 1 );
        }
        for(char c : b.toCharArray()) {
            int count = map.getOrDefault(c, 0);
            if(count  == 0 ) {return false ; }
            else {map.put(c, count - 1 ) ; }
        }

        return true;
    }

}

Methode 2 :

    public class Method2 {
public static void main(String[] args) {
    String a = "protijayi";
    String b = "jayiproti";

    System.out.println(isAnagram(a, b));// output=> true
}

private static boolean isAnagram(String a, String b) {

    int[] alphabet = new int[26];
    for(int i = 0 ; i < a.length() ;i++) {
         alphabet[a.charAt(i) - 'a']++ ;
    }
    for (int i = 0; i < b.length(); i++) {
         alphabet[b.charAt(i) - 'a']-- ;
    }

    for(  int w :  alphabet ) {
         if(w != 0 ) {return false;}
    }
    return true;

}
}

Methode 3 :

    public class Method3 {
public static void main(String[] args) {
    String a = "protijayi";
    String b = "jayiproti";

    System.out.println(isAnagram(a, b ));// output => true
}

private static boolean isAnagram(String a, String b) {
    char[] ca = a.toCharArray() ;
    char[] cb = b.toCharArray();
    Arrays.sort(   ca     );

    Arrays.sort(   cb        );
    return Arrays.equals(ca , cb );
}
}

Methode 4 :

    public class Method4 {
public static void main(String[] args) {
    String a = "protijayi";
    String b = "jayiproti";
    //String c = "gini";

    System.out.println(isAnagram(a, b ));// output => true
}

private static boolean isAnagram(String a, String b) {
    Map<Integer, Integer> map = new HashMap<>();
    a.codePoints().forEach(code -> map.put(code, map.getOrDefault(code, 0) + 1));
    b.codePoints().forEach(code -> map.put(code, map.getOrDefault(code, 0) - 1));
    //System.out.println(map.values());

    for(int count : map.values()) {
       if (count<0) return false;

    }

    return true;
}
}

Answer 4

Um sicher zu sein, dass es sich bei den Zeichenketten um Anagramme handelt, müssen Sie die gesamten Zeichenketten vergleichen - wie könnte das also schneller als o(n) sein?

Answer 5

int anagram (char a[], char b[]) {

  char chars[26];
  int ana = 0;
  int i =0;

  for (i=0; i<26;i++)
        chars[i] = 0;

  if (strlen(a) != strlen(b))
        return -1;

  i = 0;
  while ((a[i] != '\0') || (b[i] != '\0')) {
        chars[a[i] - 'a']++;
        chars[b[i] - 'a']--;
        i++;
  }

  for (i=0; i<26;i++)
        ana += chars[i];

   return ana;

}

void main() {

  char *a = "chimmy\0";
  char *b = "yimmch\0";

  printf ("Anagram result is %d.\n", anagram(a,b));

}