Valid Anagram

Q: Wie hoch ist die Zeitkomplexität von „Valid Anagram“?

Das Zählen der Buchstaben benötigt O(n) Zeit und O(1) zusätzlichen Speicherplatz, da das Zählerarray unabhängig von der Länge der Zeichenketten 26 Einträge hat. Das Sortieren beider Zeichenketten benötigt O(n log n) Zeit und in der Regel O(n) Speicherplatz für die sortierten Kopien.

Q: Ist es beim Prüfen auf ein Anagramm besser, zu sortieren oder zu zählen?

Zählen ist theoretisch schneller: O(n) gegenüber O(n log n) , und es kann anhalten, sobald ein Buchstabe zu oft vorkommt. Sortieren ist kürzer zu schreiben und funktioniert unverändert für jedes Alphabet. Erwähne in einem Vorstellungsgespräch zuerst die Sortierung und verbessere sie dann durch Zählen.

LeichtHashing Sortieren

+10

Zwei Zeichenfolgen sind Anagramme, wenn die eine eine Umstellung der anderen ist: Sie verwenden dieselben Buchstaben, und jeden Buchstaben gleich oft. Du erhältst zwei Zeichenfolgen s und t, die aus englischen Kleinbuchstaben bestehen. Gib true zurück, wenn t ein Anagramm von s ist, andernfalls false.

Funktion

isAnagram(s: string, t: string) → boolean

sstring: die erste Zeichenkette, Kleinbuchstaben
tstring: die Zeichenfolge, gegen die s getestet werden soll
Gibt zurückboolean: wahr, wenn t genau die Buchstaben von s verwendet, jeden gleich oft

Einschränkungen

1 ≤ s.length, t.length ≤ 2 × 10⁴
s und t enthalten ausschließlich englische Kleinbuchstaben (a bis z).
Die beiden Längen können unterschiedlich sein.

Beispiele

Eingabe: s = "listen"t = "silent"
Ausgabe: true
Erklärung: Beide Wörter enthalten jeweils ein e, i, l, n, s und t, daher ist silent dasselbe wie listen, nur mit anders angeordneten Buchstaben.

Eingabe: s = "aabb"t = "abbb"
Ausgabe: false
Erklärung: Die Längen stimmen überein und beide verwenden nur a und b, aber aabb enthält zwei a-Zeichen und abbb eines. Die Häufigkeiten müssen übereinstimmen, nicht nur die Buchstaben.

Eingabe: s = "cat"t = "cast"
Ausgabe: false
Erklärung: cast hat vier Buchstaben und cat hat drei, daher kann keine Umstellung von cat dieses Wort ergeben.

+19 versteckte Tests beim Einreichen

Weiterführende Frage

Was wäre, wenn Zeichenfolgen statt a bis z beliebige Unicode-Zeichen enthalten könnten? Wie würdest du die Zählung ändern?

Tipps

Öffne sie nacheinander. Jeder verrät ein bisschen mehr.

0 von 3 geöffnet

Lösung

Ein Anagramm behält die Häufigkeit der Buchstaben bei und wirft die Reihenfolge über Bord. Du brauchst also eine Zusammenfassung jedes Strings, die vergisst, an welcher Stelle die Buchstaben standen, sich aber merkt, wie viele es von jedem gibt. Sortieren erstellt diese Zusammenfassung in O(n log n); eine Tabelle mit 26 Zählern erstellt sie in einem Durchlauf.

Beide Zeichenfolgen sortieren

Idee

Beim Sortieren werden die Buchstaben eines Strings alphabetisch angeordnet, wobei ihre ursprüngliche Position verloren geht. listen wird zu eilnst sortiert, ebenso silent; sie sind also Anagramme. aabb bleibt aabb und abbb bleibt abbb; sie unterscheiden sich an Index 1 und sind daher keine Anagramme.

Der Test funktioniert in beide Richtungen. Wenn t eine Umstellung von s ist, enthalten beide dieselben Buchstaben in derselben Häufigkeit, sodass das Sortieren dieselbe Sequenz ergibt. Wenn die sortierten Sequenzen gleich sind, enthält t genau die Buchstaben von s.

Vergleiche zuerst die Längen: Strings unterschiedlicher Länge sind niemals Anagramme, und du überspringst beide Sortiervorgänge. Sortieren benötigt O(n log n) Zeit, und die meisten Sprachen sortieren eine Kopie der Zeichen, was O(n) zusätzlichen Speicherplatz benötigt. Bei n = 2 × 10^4 geht das schnell, aber der Zählansatz erfordert weniger Arbeit.

Algorithmus

Wenn sich die Längen von s und t unterscheiden, gib false zurück.
Kopiere die Zeichen jeder Zeichenfolge in ein Array.
Sortiere beide Arrays.
Gib true zurück, wenn die sortierten Arrays Element für Element gleich sind.

def isAnagram(s, t):
    if len(s) != len(t):
        return False
    return sorted(s) == sorted(t)

Zähle jeden Buchstaben

Idee

Es können nur 26 Buchstaben vorkommen, also benötigst du für jeden Buchstaben einen Zähler in einem Array mit 26 Elementen: Index 0 für a und Index 25 für z. Der Index eines Buchstabens ist sein Zeichencode minus dem Code von a. Durchlaufe s und erhöhe den Zähler für jeden Buchstaben um 1, dann durchlaufe t und verringere ihn um 1.

Du kannst vorzeitig abbrechen: Ein Zähler unter 0 bedeutet, dass t diesen Buchstaben häufiger verwendet hat, als er in s vorkommt. Bei aabb und abbb zeigen die Zähler nach s Folgendes an: a: 2 und b: 2. Dann nimmt t dreimal b; beim dritten Mal sinkt der Zähler für b auf -1, und du gibst sofort false zurück.

Warum reicht es aus, dass „kein Zähler negativ wurde“? Die Längen sind gleich, also ergibt die Summe der Zähler nach beiden Durchläufen 0. Wenn keiner negativ ist, müsste ein positiver Wert durch einen negativen ausgeglichen werden. Daher sind alle Zähler 0 und die Häufigkeiten stimmen überein. Deshalb ist die Längenprüfung erforderlich und nicht nur eine Abkürzung.

Jeder String wird einmal gelesen, das entspricht einer Laufzeit von O(n). Das Array enthält immer 26 Zahlen, unabhängig von der Länge; der zusätzliche Speicherbedarf beträgt also O(1).

Algorithmus

Wenn sich die Längen von s und t unterscheiden, gib false zurück.
Erstelle ein Array mit 26 Nullen.
Erhöhe für jeden Buchstaben von s seinen Zähler um 1.
Verringere für jeden Buchstaben von t seinen Zähler um 1; wenn er unter 0 fällt, gib false zurück.
Gib true zurück.

def isAnagram(s, t):
    if len(s) != len(t):
        return False
    counts = [0] * 26  # counts[0] is 'a', counts[25] is 'z'
    for ch in s:
        counts[ord(ch) - ord("a")] += 1
    for ch in t:
        index = ord(ch) - ord("a")
        counts[index] -= 1
        if counts[index] < 0:
            return False  # t uses this letter more often than s
    return True

Stolperfallen und Grenzfälle

Die meisten falschen Antworten entstehen dadurch, dass geprüft wird, welche Buchstaben vorkommen, statt wie oft sie vorkommen, oder dass die Längenprüfung weggelassen wird.

Die Buchstabenmengen vergleichen. aabb und abbb enthalten beide genau a und b, sind aber keine Anagramme.
Prüfen, ob jeder Buchstabe von t irgendwo in s vorkommt, ohne ihn abzuhaken. aab und abb bestehen diesen Test in beide Richtungen.
Bei der Zählerversion die Längenprüfung überspringen. Bei s = ab und t = a wird kein Zähler kleiner als 0, sodass der Code fälschlicherweise true zurückgeben würde.
Das Zählerarray mit dem unveränderten Zeichencode indizieren. a hat den Wert 97 und liegt damit weit hinter dem Ende eines Arrays mit 26 Elementen; ziehe zuerst den Code von a ab. Addiere in Lua und R 1, da ihre Arrays bei Index 1 beginnen.

Häufige Fragen4

Wie hoch ist die Zeitkomplexität von „Valid Anagram“?

Das Zählen der Buchstaben benötigt O(n) Zeit und O(1) zusätzlichen Speicherplatz, da das Zählerarray unabhängig von der Länge der Zeichenketten 26 Einträge hat. Das Sortieren beider Zeichenketten benötigt O(n log n) Zeit und in der Regel O(n) Speicherplatz für die sortierten Kopien.

Ist es beim Prüfen auf ein Anagramm besser, zu sortieren oder zu zählen?

Zählen ist theoretisch schneller: O(n) gegenüber O(n log n), und es kann anhalten, sobald ein Buchstabe zu oft vorkommt. Sortieren ist kürzer zu schreiben und funktioniert unverändert für jedes Alphabet. Erwähne in einem Vorstellungsgespräch zuerst die Sortierung und verbessere sie dann durch Zählen.

Wie prüfst du Anagramme, die Unicode-Zeichen enthalten?

Ersetze das Array aus 26 Zählern durch eine Hashmap, die Zeichen den jeweiligen Anzahlen zuordnet. Addiere für jedes Zeichen von s 1 und subtrahiere für jedes Zeichen von t 1. Prüfe, ob jeder Zähler am Ende 0 ist. Lies die Zeichenfolgen zeichenweise und nicht byteweise, damit ein Zeichen, das in mehreren Bytes gespeichert ist, nur einmal gezählt wird.

Warum ein Zähler-Array statt zwei verwenden?

Zwei Arrays, eines pro Zeichenkette, funktionieren ebenfalls: Zähle jedes Zeichen in jeder Zeichenkette und vergleiche dann die Arrays. Ein Array, das für s hochgezählt und für t heruntergezählt wird, benötigt nur halb so viel Speicher und ermöglicht es dir, sofort false zurückzugeben, sobald ein Zähler negativ wird – ganz ohne abschließende Vergleichsschleife.

Python

def isAnagram(s, t):
    # Schreibe hier den Code

Testfälle

Fall 1

Fall 2

Fall 3

Eingabe

s = "listen"
t = "silent"

Erwartet

true