Is Subsequence

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

Die Lösung mit zwei Zeigern benötigt O(n + m) Zeit, wobei n und m die Längen von s und t sind, und O(1) zusätzlichen Speicher. Die Schleife stoppt nach höchstens m Schritten. Die Präfixtabelle benötigt O(n × m) Zeit.

Q: Wie hängt „Is Subsequence“ mit der längsten gemeinsamen Teilsequenz zusammen?

s ist genau dann eine Teilsequenz von t , wenn ihre längste gemeinsame Teilsequenz die Länge n hat, also die von s . Die Präfixtabelle des ersten Ansatzes ist die, die du für dieses Problem erstellst. Hier musst du nur wissen, ob ganz s hineinpasst, daher reicht der Greedy-Durchlauf aus.

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, und andernfalls false. Zum Beispiel ist ace eine Teilfolge von abcde, aber aec ist es 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 innerhalb von 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 enthält alle drei Buchstaben, aber das einzige c steht vor dem einzigen e. Nachdem du das e an Index 4 verwendest, bleibt rechts davon kein c übrig.

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

Weiterführende Frage

Wenn t unverändert bleibt und du eine Million Zeichenketten s damit vergleichst, wie würdest du t vorbereiten, damit jeder Vergleich schneller ist, als ganz t 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 von t überspringen, was darauf hindeutet, viele Platzierungen von s auszuprobieren. Das ist nicht nötig: Jeden Buchstaben von s an der frühestmöglichen Stelle zuzuordnen, ist nie schlechter als jede andere Wahl. Daher genügt ein Durchlauf von links nach rechts mit zwei Zeigern.

Dynamische Programmierung über Präfixe

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

Idee

Sei dp[i][j] ein Indikator dafür, ob die ersten i Buchstaben von s in die ersten j Buchstaben von t passen. Sie passen, wenn sie bereits ohne t[j-1] passen oder wenn s[i-1] gleich t[j-1] ist und die ersten i-1 Buchstaben in t[:j-1] passen. Das leere Präfix passt überall hin, und Zeile i liest nur Zeile i-1, daher reichen zwei Zeilen der Länge m+1 aus.

Die Tabelle füllt jede Zelle: Bei s mit 25.000 Buchstaben und t mit 50.000 sind das 1.25 × 10^9 Zellen.

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

Behalte einen Zeiger i auf den nächsten Buchstaben von s, den du benötigst, und nimm das erste Vorkommen davon in t, auf das du triffst. Diese Wahl ist sicher. Wenn eine gültige Platzierung ein späteres Vorkommen von s[i] verwendet, erhält man durch den Austausch mit dem frühesten Vorkommen die Reihenfolge und lässt mehr von t für den Rest von s übrig. Wenn es also eine Platzierung gibt, findet der Greedy-Ansatz sie.

Die Schleife liest jeden Buchstaben von t höchstens einmal und behält zwei Indizes: Zeitaufwand O(n + m) und Speicherbedarf O(1).

Algorithmus

Setze i = 0 für s und j = 0 für t.
Vergleiche, solange sich beide Indizes innerhalb ihrer Zeichenketten befinden, s[i] mit t[j].
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

Jeden Buchstaben von s irgendwo in t suchen, statt erst nach dem vorherigen Treffer. Dadurch wird aec in abcde akzeptiert.
Einen Buchstaben zweimal verwenden. noon ist keine Teilsequenz von moon: Das einzige n an Index 3 kann nicht gleichzeitig der erste und der letzte Buchstabe sein.
Zurückgeben, ob j das Ende von t erreicht hat. Die Schleife endet oft dort, unabhängig davon, ob s gefunden wurde; nur i gibt dir darüber Auskunft.
Nicht anhalten, wenn t aufgebraucht ist. abc im Vergleich mit ab muss false zurückgeben.
s[i] lesen, nachdem i das Ende von s erreicht hat. In Python oder Java löst dieser Lesezugriff einen Fehler aus. Prüfe also i, bevor du vergleichst.

Häufige Fragen3

Wie hoch ist die Zeitkomplexität von Is Subsequence?

Die Lösung mit zwei Zeigern benötigt O(n + m) Zeit, wobei n und m die Längen von s und t sind, und O(1) zusätzlichen Speicher. Die Schleife stoppt nach höchstens m Schritten. Die Präfixtabelle benötigt O(n × m) Zeit.

Wie hängt „Is Subsequence“ mit der längsten gemeinsamen Teilsequenz zusammen?

s ist genau dann eine Teilsequenz von t, wenn ihre längste gemeinsame Teilsequenz die Länge n hat, also die von s. Die Präfixtabelle des ersten Ansatzes ist die, die du für dieses Problem erstellst. Hier musst du nur wissen, ob ganz s hineinpasst, daher reicht der Greedy-Durchlauf aus.

Was ist der Unterschied zwischen einer Teilfolge und einem Teilstring?

Ein Teilstring ist ein Block aufeinanderfolgender Buchstaben, während eine Teilsequenz Buchstaben überspringen darf, solange die Reihenfolge gleich bleibt. ace ist eine Teilsequenz von abcde, aber kein Teilstring davon. Jeder Teilstring ist eine Teilsequenz, aber nicht umgekehrt.

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

Test #1

Test #2

Test #3

Argumente

s = "ace"
t = "abcde"

Erwartete Ausgabe

true