Permutation in String
Eine Permutation eines Strings verwendet dieselben Buchstaben in beliebiger Reihenfolge, jeden so oft wie im Original: tar, rat und art sind Permutationen voneinander. Du erhältst zwei Strings s1 und s2, die aus englischen Kleinbuchstaben bestehen. Gib true zurück, wenn eine Permutation von s1 in s2 als Teilzeichenfolge (eine Folge aufeinanderfolgender Zeichen) vorkommt, andernfalls false.
Funktion
- s1string
- die Buchstaben zum Umstellen
- s2string
- die Zeichenfolge, in der gesucht werden soll
- Gibt zurückboolean
- true, wenn eine Teilzeichenfolge von s2 eine Umordnung von s1 ist
Einschränkungen
1 ≤ s1.length ≤ 2 × 1041 ≤ s2.length ≤ 5 × 104s1unds2enthalten nur englische Kleinbuchstaben (abisz).s1kann länger sein alss2.
Beispiele
- Eingabe
- s1 = "tar"s2 = "smartphone"
- Ausgabe
- true
- Erklärung
- Die Teilzeichenfolge
artan den Indizes 2 bis 4 vonsmartphoneenthält eina, einrund eint, dieselben Buchstaben wietar.
- Eingabe
- s1 = "noon"s2 = "onion"
- Ausgabe
- false
- Erklärung
- Die Teilzeichenfolgen der Länge 4 sind
onioundnion. Fürnoonbraucht man zweinund zweio, und jedes Fenster enthält stattdessen eini. Jeder Buchstabe vonnoonkommt inonionvor, aber kein Fenster hat die richtigen Anzahlen.
- Eingabe
- s1 = "abcd"s2 = "dcb"
- Ausgabe
- false
- Erklärung
- Jede Permutation von
abcdhat 4 Buchstaben, unddcbhat nur 3, daher kanndcbkeine davon enthalten.
+17 versteckte Tests beim Einreichen
Weiterführende Frage
Kannst du alle Indizes von s2 zurückgeben, an denen eine Permutation von s1 beginnt, und das weiterhin in O(m + n)-Zeit?
Tipps
Öffne sie nacheinander. Jeder verrät ein bisschen mehr.
Bei einer Permutation spielt die Reihenfolge der Buchstaben keine Rolle. Woran erkennt man bei einem Teilstring von
s2, ob er eine Permutation vons1ist, und wie lang muss er sein?Nur Teilzeichenfolgen der Länge
m = s1.lengthkommen infrage, und eine solche Teilzeichenfolge ist genau dann eine Permutation vons1, wenn ihre 26 Buchstabenhäufigkeiten den Häufigkeiten vons1entsprechen.Verschiebe ein Fenster der Länge
mübers2. Bei jedem Schritt kommt rechts ein Buchstabe hinzu und links fällt einer weg. Aktualisiere daher die Häufigkeiten im Fenster mit einem +1 und einem -1, anstatt sie neu zu zählen, und vergleiche sie mit den Häufigkeiten vons1.
Lösung
Die Permutationen von s1 aufzulisten, ist aussichtslos: Bereits 10 Buchstaben haben 3.628.800 Anordnungen. Der Ausweg besteht darin, sich nicht mehr um die Reihenfolge zu kümmern. Eine Teilzeichenfolge von s2 ist genau dann eine Permutation von s1, wenn sie dieselbe Länge m und dieselbe Anzahl jedes Buchstabens hat. Jeder Kandidat ist also ein Fenster derselben festen Länge, und du kannst ein Fenster über s2 schieben und bei jedem Schritt die Buchstabenzählungen aktualisieren, indem du einen Buchstaben hinzufügst und einen entfernst.
Jedes Fenster von Grund auf neu zählen
Korrekt, wird aber bei den größten Tests nicht fertig
Idee
Der wörtliche Ansatz, jede Permutation von s1 zu bilden und danach zu suchen, scheitert sofort: 20 Buchstaben haben mehr als 2 × 10^18 mögliche Anordnungen. Kehre die Frage stattdessen um. Eine Teilzeichenfolge von s2 ist eine Permutation von s1, wenn sie genau m Buchstaben enthält und jeden Buchstaben genauso oft verwendet wie s1. Die Reihenfolge darin spielt keine Rolle.
Zähle also die Buchstaben von s1 einmal in einer Tabelle mit 26 Zahlen, mit Index 0 für a und 25 für z. Nimm dann jede Teilzeichenfolge der Länge m aus s2, zähle ihre Buchstaben in einer neuen Tabelle und vergleiche die beiden Tabellen. Für tar in smartphone lauten die Fenster sma, mar, art und so weiter, und art stimmt überein: ein a, ein r, ein t.
Das ist korrekt, weil jeder mögliche Kandidat geprüft wird. Es ist langsam, weil benachbarte Fenster m-1 Buchstaben gemeinsam haben und du alle erneut zählst. Bei m = 15,000 und n = 50,000 gibt es 35,001 Fenster mit jeweils 15,000 Buchstaben, also etwa 5 × 10^8 Schritte.
Algorithmus
- Wenn
s1länger alss2ist, gibfalsezurück. - Zähle die Buchstaben von
s1in einer Tabelleneedmit 26 Nullen. - Zähle für jeden Startindex von 0 bis
n-mdie Buchstaben dermZeichen ab diesem Startindex in einer neuen Tabelle. - Wenn diese Tabelle gleich
needist, gibtruezurück. - Gib nach dem letzten Fenster
falsezurück.
def checkInclusion(s1, s2):
m, n = len(s1), len(s2)
if m > n:
return False
need = [0] * 26 # need[0] is 'a', need[25] is 'z'
for ch in s1:
need[ord(ch) - 97] += 1
for start in range(n - m + 1):
# Count the letters of s2[start : start + m] from scratch
window = [0] * 26
for i in range(start, start + m):
window[ord(s2[i]) - 97] += 1
if window == need:
return True
return FalseSchiebe das Fenster und vergleiche 26 Zählwerte
Idee
Zwei benachbarte Fenster unterscheiden sich nur in zwei Buchstaben. Beim Wechsel von mar zu art wird links das m entfernt und rechts das t hinzugefügt. Behalte also eine Tabelle für das aktuelle Fenster bei und aktualisiere sie bei jedem Schritt mit einem +1 und einem -1, statt die m Buchstaben erneut zu zählen.
Fülle need mit s1 und window mit den ersten m Buchstaben von s2 und vergleiche die beiden. Füge dann für jedes i von m bis n-1 s2[i] hinzu, entferne s2[i-m] und vergleiche erneut. Das Fenster ist nun s2[i-m+1..i] und weiterhin m Buchstaben lang.
Jeder Schritt erfordert zwei Aktualisierungen und einen Vergleich von 26 Zahlen, unabhängig davon, was m ist. Bei der größten Eingabe sind das etwa 26 × 50,000 = 1.3 × 10^6 Operationen, also eine lineare Laufzeit bezogen auf die Länge von s2. Das ist die Lösung, die die meisten Interviewer erwarten.
Algorithmus
- Wenn
s1länger alss2ist, gibfalsezurück. - Zähle
s1inneedund die erstenmBuchstaben vons2inwindow. - Wenn die beiden Tabellen gleich sind, gib
truezurück. - Für jedes
ivonmbisn-1: Addiere 1 fürs2[i], subtrahiere 1 fürs2[i-m]und gibtruezurück, wenn die Tabellen gleich sind. - Gib
falsezurück.
def checkInclusion(s1, s2):
m, n = len(s1), len(s2)
if m > n:
return False
need = [0] * 26
window = [0] * 26
for i in range(m):
need[ord(s1[i]) - 97] += 1
window[ord(s2[i]) - 97] += 1 # the first window is s2[0 : m]
if window == need:
return True
for i in range(m, n):
window[ord(s2[i]) - 97] += 1 # s2[i] enters on the right
window[ord(s2[i - m]) - 97] -= 1 # s2[i - m] leaves on the left
if window == need:
return True
return FalseVerschiebe das Fenster und verfolge unausgeglichene Buchstaben
Idee
Bei jedem Schritt 26 Zahlen zu vergleichen, wiederholt Arbeit, denn ein Schritt ändert nur zwei davon. Verwende stattdessen eine Tabelle balance: balance[c] gibt an, wie viele Exemplare des Buchstabens c in s1 vorkommen, abzüglich der Anzahl im Fenster. Das Fenster ist genau dann eine Permutation von s1, wenn alle 26 Werte 0 sind. Führe neben der Tabelle unbalanced, die Anzahl der Buchstaben, deren Wert nicht 0 ist, und gib true zurück, sobald dieser Wert 0 erreicht.
Für die Buchführung gilt eine Regel. Bevor du balance[c] änderst: Wenn der Wert 0 ist, wird der Buchstabe gerade unausgeglichen, also erhöhst du unbalanced um 1. Nach der Änderung gilt: Wenn der Wert 0 ist, ist der Buchstabe ausgeglichen, also verringerst du unbalanced um 1. Ein Buchstabe, der ins Fenster kommt, verringert seinen Wert um 1; ein Buchstabe, der das Fenster verlässt, erhöht ihn um 1. Wenn sich ein Wert von 2 auf 1 ändert, wird keine der beiden Prüfungen ausgelöst. Das ist richtig: Der Buchstabe war unausgeglichen und ist es weiterhin.
Gehe tar und smartphone durch. Zu Beginn sind die Werte a: 1, r: 1, t: 1, also ist unbalanced gleich 3. s und m kommen hinzu und erhöhen den Wert auf 5; dann kommt a hinzu und bringt a auf 0: 4. r kommt hinzu (3), während s das Fenster verlässt (2). t kommt hinzu (1), während m das Fenster verlässt (0), und das Fenster art ist die Antwort.
Du kannst unbalanced == 0 bereits ab dem ersten Buchstaben prüfen. Solange das Fenster weniger als m Buchstaben enthält, ergibt die Summe der Werte eine positive Zahl, daher ist mindestens einer davon nicht 0. Jeder Schritt erfordert eine feste Menge an Arbeit, also hat der gesamte Durchlauf eine Laufzeit von O(m + n), und die Tabelle enthält immer 26 Zahlen, benötigt also O(1) Speicherplatz.
Algorithmus
- Wenn
s1länger alss2ist, gibfalsezurück. - Zähle die Buchstaben in
s1inbalanceund setzeunbalancedauf die Anzahl der Buchstaben, deren Bilanz nicht 0 ist. - Ziehe für jeden Index
ivons21 von der Bilanz vons2[i]ab, erhöheunbalancedum 1, wenn diese Bilanz 0 war, und verringere es um 1, wenn sie 0 wird. - Wenn
i ≥ mgilt, erhöhe die Bilanz vons2[i-m]um 1 und aktualisiere die Bilanz entsprechend. - Wenn
unbalanced0 ist, gibtruezurück. Gib nach der Schleifefalsezurück.
def checkInclusion(s1, s2):
m, n = len(s1), len(s2)
if m > n:
return False
# balance[c]: copies of letter c in s1 minus copies in the window
balance = [0] * 26
for ch in s1:
balance[ord(ch) - 97] += 1
unbalanced = sum(1 for b in balance if b != 0)
for i in range(n):
# s2[i] enters the window on the right
c = ord(s2[i]) - 97
if balance[c] == 0:
unbalanced += 1
balance[c] -= 1
if balance[c] == 0:
unbalanced -= 1
# s2[i - m] leaves on the left once the window would pass m letters
if i >= m:
c = ord(s2[i - m]) - 97
if balance[c] == 0:
unbalanced += 1
balance[c] += 1
if balance[c] == 0:
unbalanced -= 1
if unbalanced == 0:
return True
return False
Stolperfallen und Grenzfälle
Die meisten falschen Antworten entstehen an den Rändern des Fensters oder dadurch, dass geprüft wird, welche Buchstaben vorkommen, statt wie oft sie vorkommen.
- Es wird nur geprüft, ob jeder Buchstabe von
s1im Fenster vorkommt.onioenthält jeden Buchstaben vonnoon, ist aber keine Permutation davon. Vergleiche die Häufigkeiten. - Der falsche Buchstabe wird entfernt. Wenn
s2[i]hinzukommt, ist der Buchstabe, der herausfällt,s2[i-m], sodass das Fenster zus2[i-m+1..i]wird. Wenns2[i-m+1]entfernt wird, enthält das Fenster nur nochm-1Buchstaben. - Das erste Fenster wird übersprungen. Wenn du erst nach dem Verschieben vergleichst, wird eine Permutation am Index 0 nie gefunden.
- Der Fall, dass
s1länger alss2ist, wird vergessen. In Rust führtn - mbei vorzeichenlosen Längen zu einem Underflow, und in Swift stürzt der Bereich0...(n - m)ab. Gib zuerstfalsezurück. - Arrays werden mit
==in einer Sprache verglichen, in der damit Referenzen verglichen werden. In JavaScript und Dart sind zwei verschiedene Arrays niemals==; verwende in JavaArrays.equals.
Häufige Fragen4
Wie hoch ist die Zeitkomplexität von „Permutation in String“?
Mit einem gleitenden Fenster beträgt die Laufzeit O(m + n), wobei m die Länge von s1 und n die Länge von s2 ist. Du zählst s1 einmal, dann tritt jeder Buchstabe von s2 einmal in das Fenster ein und verlässt es einmal. Jedes Fenster von Grund auf neu zu zählen, kostet stattdessen O(n · m).
Ist „Permutation in String“ dasselbe wie das Finden eines Anagramms in einer Zeichenfolge?
Ja. Eine Permutation von s1 ist ein Anagramm davon. Die Frage ist also, ob ein Teilstring der Länge m von s2 ein Anagramm von s1 ist. Beim Anagrammvergleich zweier vollständiger Zeichenfolgen werden die Buchstabenhäufigkeiten einmal verglichen; hier wird derselbe Vergleich auf ein Fenster angewendet, das entlang von s2 verschoben wird.
Warum hat das gleitende Fenster hier eine feste Größe?
Jede Permutation von s1 hat genau m Buchstaben, daher können nur Fenster der Länge m übereinstimmen. Bei Problemen wie dem längsten Teilstring ohne Wiederholungen wird das Fenster vergrößert und verkleinert; hier bewegen sich beide Ränder gemeinsam, jeweils um einen Schritt.
Kann ich anstelle eines Arrays mit 26 Zählern eine Hash-Map verwenden?
Ja, und du brauchst eine, wenn die Zeichenfolgen beliebige Zeichen enthalten können. Bei ausschließlich Kleinbuchstaben ist ein Array der Länge 26 schneller und benötigt konstanten Speicherplatz. Bei einer Map solltest du einen Schlüssel löschen, wenn sein Zähler auf 0 sinkt, damit zwei Maps mit denselben Buchstaben als gleich gelten, oder du behältst den unbalanced-Zähler aus dem letzten Ansatz bei, der mit einer Map genauso funktioniert.
Ähnliche Aufgaben
Aufgaben mit denselben Ideen. Wer zwei oder drei davon löst, behält das Muster.
Python
def checkInclusion(s1, s2):
# Schreibe hier den CodeFall 1
Fall 2
Fall 3
Eingabe
s1 = "tar" s2 = "smartphone"
Erwartet
true