Is Subsequence

Q: Jaka jest złożoność czasowa 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 wymaga dodatkowej pamięci O(1) . Pętla kończy działanie po co najwyżej m krokach. Utworzenie tablicy prefiksów zajmuje czas O(n × m) .

Q: Jaki jest związek między problemem podciągu a najdłuższym wspólnym podciągiem?

s jest podciągiem t wtedy i tylko wtedy, gdy ich najdłuższy wspólny podciąg ma długość n , czyli długość całego s . Tablica prefiksów z pierwszego podejścia to ta, którą tworzysz dla tamtego problemu. Tutaj musisz tylko wiedzieć, czy całe s pasuje, więc wystarczy zachłanne przejście.

Ł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 litery (możesz nie usuwać ż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: prawda, jeśli s można odczytać w t w tej samej kolejności, ale 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 ma 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 na indeksie 0, liter o na indeksach 1 i 4 oraz n na indeksie 6 w monsoon. Litery pomiędzy nimi są usuwane.

Pytanie dodatkowe

Jeśli t pozostaje niezmienne i sprawdzasz milion ciągów znaków s pod jego kątem, jak przygotujesz t, aby każde sprawdzenie było szybsze niż odczytanie 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ć litery z t w dowolnym miejscu, co sugeruje wypróbowanie wielu rozmieszczeń s. Nie musisz tego robić: dopasowanie każdej litery z s w najwcześniejszym możliwym miejscu nigdy nie jest gorsze od żadnego innego wyboru, więc wystarczy jedno przejście od lewej do prawej z użyciem dwóch wskaźników.

Programowanie dynamiczne na prefiksach

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

Intuicja

Niech dp[i][j] określa, czy pierwsze i liter ciągu s mieszczą się w pierwszych j literach ciągu t. Mieszczą się, jeśli mieszczą się już bez t[j-1] albo jeśli s[i-1] jest równe t[j-1] i pierwsze i-1 liter mieszczą się w t[:j-1]. Pusty prefiks mieści się wszędzie, a wiersz i odwołuje się tylko do wiersza i-1, więc wystarczą dwa wiersze o długości m+1.

Tablica wypełnia każdą komórkę: dla s o długości 25,000 liter i t o długości 50,000 liter daje to 1.25 × 10^9 komórek.

Algorytm

Utwórz wiersz prev z m+1 wartościami, wszystkie true: pusty ciąg 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 dopasowaniem

Intuicja

Zachowaj wskaźnik i wskazujący na następną literę s, której potrzebujesz, i wybierz jej pierwsze napotkane wystąpienie w t. Ten wybór jest bezpieczny. Jeśli poprawne rozmieszczenie wykorzystuje późniejsze wystąpienie s[i], zamiana go na najwcześniejsze wystąpienie zachowuje kolejność i pozostawia więcej znaków t na pozostałą część s. Zatem jeśli istnieje jakiekolwiek rozmieszczenie, algorytm zachłanny je znajdzie.

Pętla odczytuje każdą literę t najwyżej raz i przechowuje dwa indeksy: czas O(n + m) i pamięć O(1).

Algorytm

Ustaw i = 0 dla s i j = 0 dla t.
Gdy oba indeksy znajdują się wewnątrz swoich ciągów znaków, porównaj s[i] z t[j].
Jeśli są równe, zwiększ i.
W każdym przypadku 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

Wyszukiwanie każdej litery z s w dowolnym miejscu w t, zamiast po poprzednim dopasowaniu. W ten sposób aec zostanie uznane za podciąg abcde.
Użycie tej samej kopii litery dwa razy. noon nie jest podciągiem moon: jedyne n, na indeksie 3, nie może być jednocześnie pierwszą i ostatnią literą.
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 ci tę informację.
Niezatrzymywanie się, gdy zabraknie znaków w t. Dla abc i ab należy zwrócić false.
Odczytywanie s[i], gdy 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 pytania3

Jaka jest złożoność czasowa 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 wymaga dodatkowej pamięci O(1). Pętla kończy działanie po co najwyżej m krokach. Utworzenie tablicy prefiksów zajmuje czas O(n × m).

Jaki jest związek między problemem podciągu a najdłuższym wspólnym podciągiem?

s jest podciągiem t wtedy i tylko wtedy, gdy ich najdłuższy wspólny podciąg ma długość n, czyli długość całego s. Tablica prefiksów z pierwszego podejścia to ta, którą tworzysz dla tamtego problemu. Tutaj musisz tylko wiedzieć, czy całe s pasuje, więc wystarczy zachłanne przejście.

Jaka jest różnica między podciągiem a podłańcuchem?

Podciąg jest blokiem kolejnych liter, natomiast podciąg sekwencji może pomijać litery, o ile ich kolejność pozostaje taka sama. ace jest podciągiem sekwencji abcde, ale nie jest jego podciągiem ciągłym. Każdy podciąg ciągły jest podciągiem sekwencji, ale nie odwrotnie.

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

Test #1

Test #2

Test #3

Argumenty

s = "ace"
t = "abcde"

Oczekiwany wynik

true