Is Subsequence

Q: C jaka jest złożoność czasowa funkcji Is Subsequence?

Rozwiązanie z dwoma wskaźnikami działa w czasie O(n + m) , gdzie n i m to długości s i t , i wykorzystuje O(1) dodatkowej pamięci. W praktyce pętla zatrzymuje się po co najwyżej m krokach. Tablica prefiksów wymaga czasu O(n × m) .

Q: Dlaczego zachłanne podejście z dwoma wskaźnikami działa w problemie „Is Subsequence”?

Dopasowanie litery z s w jej najwcześniejszym możliwym miejscu w t pozostawia najdłuższą możliwą pozostałą część t dla pozostałych liter. Każde dopasowanie wykorzystujące późniejszą kopię można zmienić tak, by używało wcześniejszej, nie naruszając kolejności, więc jeśli istnieje jakiekolwiek dopasowanie, zachłanny algorytm je znajdzie.

Q: Jak szybko sprawdzić wiele ciągów znaków względem tego samego t?

Przygotuj t raz: dla każdej litery zapisz posortowaną listę indeksów, pod którymi występuje. Aby dopasować s[i] , wyszukaj binarnie na liście tej litery pierwszy indeks po poprzednim dopasowaniu. Każde sprawdzenie zajmuje wtedy O(n log m) zamiast O(m) .

ŁatweDwa wskaźniki

+10

Otrzymujesz dwa ciągi znaków, s i t. Zwróć true, jeśli możesz przekształcić t w s, usuwając niektóre z jego liter (być może żadnej), tak aby pozostałe litery zachowały swoją kolejność, a w przeciwnym razie zwróć false. Na przykład ace jest podciągiem abcde, ale aec nim nie jest.

Funkcja

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

sstring: ciąg znaków, którego należy szukać
tstring: ciąg znaków, z którego należy usunąć litery
Zwracaboolean: true, jeśli s można odczytać w t po kolei, z możliwymi przerwami

Ograniczenia

1 ≤ s.length ≤ 3 × 10⁴
1 ≤ t.length ≤ 5 × 10⁴
s i t zawierają wyłącznie małe litery alfabetu angielskiego.

Przykłady

Wejście: s = "ace"t = "abcde"
Wyjście: true
Wyjaśnienie: Usuń b i d z abcde, a pozostanie ace, w tej samej kolejności.

Wejście: s = "aec"t = "abcde"
Wyjście: false
Wyjaśnienie: t zawiera wszystkie trzy litery, ale jedyne c znajduje się przed jedynym e. Po użyciu e o indeksie 4 po jego prawej stronie nie zostaje już żadne c.

Wejście: s = "moon"t = "monsoon"
Wyjście: true
Wyjaśnienie: Użyj m o indeksie 0, liter o o indeksach 1 i 4 oraz n o indeksie 6 w słowie monsoon. Litery pomiędzy nimi są usuwane.

+20 ukrytych testów przy wysłaniu

Pytanie dodatkowe

Załóżmy, że t pozostaje bez zmian i musisz sprawdzić milion różnych ciągów znaków s pod jego kątem. Jak przygotujesz t, aby każde sprawdzenie było szybsze niż ponowne odczytywanie całego t?

Podpowiedzi

Otwieraj je po kolei. Każda zdradza trochę więcej.

Otwarte: 0 z 3

Rozwiązanie

Podciąg może pomijać dowolne litery z t, więc może się wydawać, że trzeba wypróbować wiele sposobów umieszczenia s w t. Nie trzeba. Dopasowanie każdej litery z s w najwcześniejszym możliwym miejscu nigdy nie jest gorsze od żadnego innego wyboru, a dzięki temu wyszukiwanie sprowadza się do jednego przejścia od lewej do prawej z użyciem dwóch wskaźników.

Programowanie dynamiczne po prefiksach

Poprawne, ale nie kończy się na największych testach

Intuicja

Zadaj mniejsze pytanie: czy pierwsze i liter ciągu s mieści się w pierwszych j literach ciągu t? Oznacz odpowiedź jako dp[i][j]. Jeśli mieszczą się w t[:j-1], to mieszczą się również w t[:j], ponieważ możesz usunąć t[j-1]. Jeśli s[i-1] jest równe t[j-1], możesz też użyć tej litery, a wtedy pierwsze i-1 liter ciągu s muszą zmieścić się w t[:j-1]. Zatem dp[i][j] = dp[i][j-1] or (s[i-1] == t[j-1] and dp[i-1][j-1]), a pusty prefiks ciągu s mieści się wszędzie.

Wiersz i odczytuje tylko wiersz i-1, więc wystarczą dwa wiersze o długości m+1. Odpowiedzią jest ostatnia komórka ostatniego wiersza.

To ta sama tabela, którą tworzysz dla najdłuższego wspólnego podciągu. Jest poprawna, ale wypełnia każdą komórkę. Dla ciągu s o długości 25,000 liter i ciągu t o długości 50,000 daje to 1.25 × 10^9 komórek — znacznie więcej, niż potrzeba do pojedynczego przejścia przez oba ciągi.

Algorytm

Utwórz wiersz prev z m+1 wartościami, wszystkie true: pusty s pasuje do każdego prefiksu t.
Dla każdego i od 1 do n utwórz wiersz cur z cur[0] = false.
Dla każdego j od 1 do m ustaw cur[j] na cur[j-1] albo na prev[j-1], gdy s[i-1] jest równe t[j-1].
Zastąp prev przez cur.
Zwróć prev[m].

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]

Dwa wskaźniki z zachłannym dopasowywaniem

Intuicja

Przeglądaj t od lewej do prawej i przechowuj wskaźnik i na następną literę s, której nadal potrzebujesz. Gdy t[j] jest równe s[i], wykorzystaj tę literę i przesuń i dalej. Tak czy inaczej, przesuń j dalej. Jeśli i dotrze do końca s, każda litera znalazła swoje miejsce we właściwej kolejności.

Dlaczego wybranie pierwszego dopasowania jest bezpieczne? Załóżmy, że w pewnym poprawnym rozmieszczeniu użyto późniejszego wystąpienia s[i]. Zastąpienie go najwcześniejszym wystąpieniem zachowuje kolejność i pozostawia więcej znaków t po prawej stronie dla pozostałych liter s, więc zachłanny wybór nigdy nie eliminuje istniejącego rozmieszczenia. Dla moon w monsoon wskaźnik wybiera o o indeksie 1, pomija n i s, wybiera o o indeksie 4 i kończy na n o indeksie 6.

j odwiedza każdą literę t raz, a i przesuwa się tylko do przodu, więc pętla wykonuje się najwyżej m razy. Wystarczą dwa indeksy.

Algorytm

Ustaw i = 0 dla s i j = 0 dla t.
Dopóki oba indeksy znajdują się w swoich ciągach znaków, porównuj s[i] z t[j].
Jeśli są równe, zwiększ i.
Za każdym razem zwiększ j.
Zwróć informację, czy i jest równe długości s.

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)

Pułapki i przypadki brzegowe

Pętla z dwoma wskaźnikami jest krótka, a jej błędy kryją się na brzegach.

Wyszukiwanie każdej litery z s w dowolnym miejscu w t zamiast za poprzednim dopasowaniem. To akceptuje aec w abcde, gdzie kolejność jest zaburzona.
Użycie tego samego wystąpienia litery dwa razy. noon nie jest podciągiem moon: moon zawiera tylko jedno n, na indeksie 3, więc nie może ono być jednocześnie pierwszą i ostatnią literą noon.
Zwracanie informacji, czy j dotarło do końca t. Pętla często kończy się w tym miejscu niezależnie od tego, czy znaleziono s; tylko i daje tę informację.
Zapominanie, że s może być dłuższe niż t. Dla abc w porównaniu z ab należy zwrócić false, co zapewnia pętla, o ile zatrzymuje się, gdy skończy się t.
Odczytanie s[i] po tym, jak i dotarło do końca s. W Pythonie lub Javie taki odczyt zgłasza wyjątek, więc przed porównaniem sprawdź i.

Najczęstsze pytania4

C jaka jest złożoność czasowa funkcji Is Subsequence?

Rozwiązanie z dwoma wskaźnikami działa w czasie O(n + m), gdzie n i m to długości s i t, i wykorzystuje O(1) dodatkowej pamięci. W praktyce pętla zatrzymuje się po co najwyżej m krokach. Tablica prefiksów wymaga czasu O(n × m).

Dlaczego zachłanne podejście z dwoma wskaźnikami działa w problemie „Is Subsequence”?

Dopasowanie litery z s w jej najwcześniejszym możliwym miejscu w t pozostawia najdłuższą możliwą pozostałą część t dla pozostałych liter. Każde dopasowanie wykorzystujące późniejszą kopię można zmienić tak, by używało wcześniejszej, nie naruszając kolejności, więc jeśli istnieje jakiekolwiek dopasowanie, zachłanny algorytm je znajdzie.

Jak szybko sprawdzić wiele ciągów znaków względem tego samego t?

Przygotuj t raz: dla każdej litery zapisz posortowaną listę indeksów, pod którymi występuje. Aby dopasować s[i], wyszukaj binarnie na liście tej litery pierwszy indeks po poprzednim dopasowaniu. Każde sprawdzenie zajmuje wtedy O(n log m) zamiast O(m).

Czym różni się podciąg od podciągu spójnego?

Podciąg to blok kolejnych liter, natomiast podciąg może pomijać litery, o ile ich kolejność pozostaje taka sama. ace jest podciągiem abcde, ale nie jest jego podciągiem spójnym. Każdy podciąg spójny jest podciągiem, ale nie odwrotnie.

Python

def isSubsequence(s, t):
    # Napisz kod tutaj

Przypadki testowe

Przypadek 1

Przypadek 2

Przypadek 3

Wejście

s = "ace"
t = "abcde"

Oczekiwane

true