Is Subsequence

Q: Wie hoch ist die Zeitkomplexität von Is Subsequence?

Die Lösung mit zwei Zeigern läuft in O(n + m) Zeit, wobei n und m die Längen von s und t sind, und benötigt O(1) zusätzlichen Speicherplatz. In der Praxis endet die Schleife nach höchstens m Schritten. Die Präfixtabelle benötigt O(n × m) Zeit.

Q: Warum funktioniert der greedy Zwei-Zeiger-Ansatz für Is Subsequence?

Wenn ein Buchstabe aus s an seiner frühestmöglichen Stelle in t zugeordnet wird, bleibt der längstmögliche Rest von t für die übrigen Buchstaben. Jede Zuordnung, die ein späteres Vorkommen verwendet, kann so geändert werden, dass sie das frühere verwendet, ohne die Reihenfolge zu verletzen. Wenn also eine Zuordnung existiert, findet die gierige Zuordnung sie.

Q: Wie überprüfst du schnell viele Zeichenketten mit demselben t?

Bereite t einmal vor: Speichere für jeden Buchstaben die sortierte Liste der Indizes, an denen er vorkommt. Um s[i] zu platzieren, durchsuche die Liste dieses Buchstabens binär nach dem ersten Index nach dem vorherigen Treffer. Jeder Test kostet dann O(n log m) statt O(m) .

LeichtZwei Zeiger

+10

Du erhältst zwei Zeichenfolgen, s und t. Gib true zurück, wenn du t in s umwandeln kannst, indem du einige seiner Buchstaben löschst (möglicherweise auch keine), während die verbleibenden Buchstaben ihre Reihenfolge beibehalten, andernfalls false. Beispielsweise ist ace eine Teilsequenz von abcde, aber aec nicht.

Funktion

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

sstring: die zu suchende Zeichenfolge
tstring: die Zeichenfolge, aus der Buchstaben gelöscht werden sollen
Gibt zurückboolean: wahr, wenn s in t der Reihenfolge nach gelesen werden kann, möglicherweise mit Lücken

Einschränkungen

1 ≤ s.length ≤ 3 × 10⁴
1 ≤ t.length ≤ 5 × 10⁴
s und t enthalten nur englische Kleinbuchstaben.

Beispiele

Eingabe: s = "ace"t = "abcde"
Ausgabe: true
Erklärung: Wenn du b und d aus abcde löschst, bleibt ace in derselben Reihenfolge übrig.

Eingabe: s = "aec"t = "abcde"
Ausgabe: false
Erklärung: t hat alle drei Buchstaben, aber das einzige c steht vor dem einzigen e. Nachdem du das e an Index 4 verwendet hast, bleibt rechts davon kein c mehr übrig.

Eingabe: s = "moon"t = "monsoon"
Ausgabe: true
Erklärung: Verwende das m an Index 0, die os an den Indizes 1 und 4 sowie das n an Index 6 von monsoon. Die Buchstaben dazwischen werden gelöscht.

+20 versteckte Tests beim Einreichen

Weiterführende Frage

Angenommen, t bleibt gleich und du musst eine Million verschiedene Zeichenketten s damit vergleichen. Wie würdest du t vorbereiten, damit jeder Vergleich schneller geht, als t jedes Mal wieder vollständig zu lesen?

Tipps

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

0 von 3 geöffnet

Lösung

Eine Teilsequenz darf an beliebigen Stellen Buchstaben aus t überspringen, sodass es so aussehen kann, als müsstest du viele Möglichkeiten ausprobieren, s in t einzufügen. Das musst du nicht. Jeden Buchstaben von s an der frühestmöglichen Stelle zu finden, ist nie schlechter als jede andere Wahl. Dadurch wird die Suche zu einem einzigen Durchlauf von links nach rechts mit zwei Zeigern.

Dynamische Programmierung über Präfixe

Korrekt, wird aber bei den größten Tests nicht fertig

Idee

Stelle eine kleinere Frage: Passen die ersten i Buchstaben von s in die ersten j Buchstaben von t? Nenne die Antwort dp[i][j]. Wenn sie in t[:j-1] passen, passen sie auch in t[:j], da du t[j-1] löschen kannst. Wenn s[i-1] gleich t[j-1] ist, kannst du diesen Buchstaben ebenfalls verwenden. Dann müssen die ersten i-1 Buchstaben von s in t[:j-1] passen. Also gilt dp[i][j] = dp[i][j-1] or (s[i-1] == t[j-1] and dp[i-1][j-1]), und das leere Präfix von s passt überall hinein.

Zeile i liest nur Zeile i-1, daher reichen zwei Zeilen der Länge m+1 aus. Die Antwort ist die letzte Zelle der letzten Zeile.

Das ist dieselbe Tabelle, die du für die längste gemeinsame Teilsequenz aufbaust, und sie ist korrekt, aber sie füllt jede Zelle aus. Bei s mit 25,000 Buchstaben und t mit 50,000 Buchstaben sind das 1.25 × 10^9 Zellen – viel mehr, als ein einziger Durchlauf über die beiden Zeichenketten erfordert.

Algorithmus

Erstelle eine Zeile prev mit m+1 Werten, die alle true sind: Ein leeres s passt in jedes Präfix von t.
Erstelle für jedes i von 1 bis n eine Zeile cur mit cur[0] = false.
Setze für jedes j von 1 bis m cur[j] auf cur[j-1] oder auf prev[j-1], wenn s[i-1] gleich t[j-1] ist.
Ersetze prev durch cur.
Gib prev[m] zurück.

def isSubsequence(s, t):
    n, m = len(s), len(t)
    # prev[j]: the first i-1 letters of s fit inside t[:j]. An empty s fits anywhere.
    prev = [True] * (m + 1)
    for i in range(1, n + 1):
        cur = [False] * (m + 1)
        for j in range(1, m + 1):
            cur[j] = cur[j - 1] or (s[i - 1] == t[j - 1] and prev[j - 1])
        prev = cur
    return prev[m]

Zwei Zeiger mit gierigem Abgleich

Idee

Lies t von links nach rechts und behalte einen Zeiger i auf den nächsten Buchstaben von s, den du noch benötigst. Wenn t[j] gleich s[i] ist, verwende ihn und rücke i vor. In jedem Fall rücke j vor. Wenn i das Ende von s erreicht, hat jeder Buchstabe in der richtigen Reihenfolge einen Platz gefunden.

Warum ist es sicher, den ersten Treffer zu nehmen? Angenommen, eine gültige Platzierung verwendet ein späteres Vorkommen von s[i]. Ersetzt man es durch das früheste Vorkommen, bleibt die Reihenfolge erhalten, und für den Rest von s bleibt rechts davon mehr von t übrig. Die gierige Wahl verliert also niemals eine vorhandene Platzierung. Bei moon in monsoon nimmt der Zeiger das o an Index 1, überspringt n und s, nimmt das o an Index 4 und landet schließlich beim n an Index 6.

j besucht jeden Buchstaben von t genau einmal, und i bewegt sich nur vorwärts. Daher läuft die Schleife höchstens m Mal. Zwei Indizes sind alles, was sie an Speicher benötigt.

Algorithmus

Setze i = 0 für s und j = 0 für t.
Vergleiche s[i] mit t[j], solange sich beide Indizes innerhalb ihrer Zeichenketten befinden.
Erhöhe i, wenn sie gleich sind.
Erhöhe j in jedem Fall.
Gib zurück, ob i der Länge von s entspricht.

def isSubsequence(s, t):
    i = j = 0
    while i < len(s) and j < len(t):
        if s[i] == t[j]:
            i += 1
        j += 1
    return i == len(s)

Stolperfallen und Grenzfälle

Die Schleife mit zwei Zeigern ist kurz, und ihre Fehler stecken an den Rändern.

Jeden Buchstaben von s irgendwo in t zu suchen, statt erst nach dem vorherigen Treffer. Dadurch wird aec in abcde akzeptiert, obwohl die Reihenfolge nicht stimmt.
Einen Buchstaben zweimal zu verwenden. noon ist keine Teilsequenz von moon: moon hat nur ein einziges n, an Index 3, und es kann nicht zugleich der erste und der letzte Buchstabe von noon sein.
Zurückzugeben, ob j das Ende von t erreicht hat. Die Schleife endet oft dort, unabhängig davon, ob s gefunden wurde; nur i sagt es dir.
Zu vergessen, dass s länger als t sein kann. Für abc gegenüber ab muss false zurückgegeben werden. Das liefert die Schleife, solange sie anhält, sobald t aufgebraucht ist.
s[i] zu lesen, nachdem i das Ende von s erreicht hat. In Python oder Java löst dieser Lesezugriff eine Ausnahme aus; prüfe also i, bevor du vergleichst.

Häufige Fragen4

Wie hoch ist die Zeitkomplexität von Is Subsequence?

Die Lösung mit zwei Zeigern läuft in O(n + m) Zeit, wobei n und m die Längen von s und t sind, und benötigt O(1) zusätzlichen Speicherplatz. In der Praxis endet die Schleife nach höchstens m Schritten. Die Präfixtabelle benötigt O(n × m) Zeit.

Warum funktioniert der greedy Zwei-Zeiger-Ansatz für Is Subsequence?

Wenn ein Buchstabe aus s an seiner frühestmöglichen Stelle in t zugeordnet wird, bleibt der längstmögliche Rest von t für die übrigen Buchstaben. Jede Zuordnung, die ein späteres Vorkommen verwendet, kann so geändert werden, dass sie das frühere verwendet, ohne die Reihenfolge zu verletzen. Wenn also eine Zuordnung existiert, findet die gierige Zuordnung sie.

Wie überprüfst du schnell viele Zeichenketten mit demselben t?

Bereite t einmal vor: Speichere für jeden Buchstaben die sortierte Liste der Indizes, an denen er vorkommt. Um s[i] zu platzieren, durchsuche die Liste dieses Buchstabens binär nach dem ersten Index nach dem vorherigen Treffer. Jeder Test kostet dann O(n log m) statt O(m).

Was ist der Unterschied zwischen einer Teilsequenz und einer Teilzeichenfolge?

Eine Teilzeichenfolge ist ein Block aufeinanderfolgender Buchstaben, während eine Teilsequenz Buchstaben überspringen darf, solange die Reihenfolge gleich bleibt. ace ist eine Teilsequenz von abcde, aber keine Teilzeichenfolge davon. Jede Teilzeichenfolge ist eine Teilsequenz, aber nicht umgekehrt.

Python

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

Testfälle

Fall 1

Fall 2

Fall 3

Eingabe

s = "ace"
t = "abcde"

Erwartet

true