Permutation in String

Q: Jaka jest złożoność czasowa Permutation in String?

W przypadku okna przesuwnego złożoność wynosi O(m + n) , gdzie m to długość s1 , a n to długość s2 . Zliczasz s1 raz, a następnie każda litera s2 raz wchodzi do okna i raz je opuszcza. Ponowne zliczanie każdego okna od początku kosztuje natomiast O(n · m) .

Q: Czy problem „Permutation in String” polega na znalezieniu anagramu w ciągu znaków?

Tak. Permutacja s1 jest jego anagramem, więc pytanie brzmi, czy jakiś podciąg s2 o długości m jest anagramem s1 . Sprawdzenie, czy dwa całe ciągi znaków są anagramami, polega na jednorazowym porównaniu liczby wystąpień liter; tutaj to samo porównanie wykonuje się dla okna przesuwającego się wzdłuż s2 .

Q: Dlaczego przesuwane okno ma tutaj stały rozmiar?

Każda permutacja s1 ma dokładnie m liter, więc dopasować mogą się tylko okna o długości m . W problemach takich jak znalezienie najdłuższego podciągu bez powtórzeń okno się powiększa i zmniejsza; tutaj oba jego brzegi przesuwają się razem, po jednym kroku.

ŚredniePrzesuwane okno Haszowanie

+10

Permutacja ciągu znaków zawiera te same litery w dowolnej kolejności, każdą tyle razy, ile występuje w oryginale: tar, rat i art są swoimi permutacjami. Otrzymujesz dwa ciągi s1 i s2, złożone z małych liter alfabetu angielskiego. Zwróć true, jeśli jakaś permutacja s1 występuje w s2 jako podciąg (ciąg kolejnych znaków), a w przeciwnym razie zwróć false.

Funkcja

checkInclusion(s1: string, s2: string) → boolean

s1string: litery do przestawienia
s2string: ciąg znaków do wyszukania
Zwracaboolean: prawda, jeśli podciąg s2 jest przestawieniem znaków s1

Ograniczenia

1 ≤ s1.length ≤ 2 × 10⁴
1 ≤ s2.length ≤ 5 × 10⁴
s1 i s2 zawierają tylko małe litery alfabetu angielskiego (od a do z).
s1 może być dłuższe niż s2.

Przykłady

Wejście: s1 = "tar"s2 = "smartphone"
Wyjście: true
Wyjaśnienie: Podciąg art na indeksach od 2 do 4 w smartphone zawiera jedną literę a, jedną r i jedną t, czyli te same litery co tar.

Wejście: s1 = "noon"s2 = "onion"
Wyjście: false
Wyjaśnienie: Podciągi o długości 4 to onio i nion. noon wymaga dwóch liter n i dwóch liter o, a w każdym oknie zamiast jednej z nich jest i. Wszystkie litery z noon występują w onion, ale żadne okno nie ma odpowiednich liczności.

Wejście: s1 = "abcd"s2 = "dcb"
Wyjście: false
Wyjaśnienie: Każda permutacja abcd ma 4 litery, a dcb ma tylko 3, więc nie może zawierać żadnej z nich.

+17 ukrytych testów przy wysłaniu

Pytanie dodatkowe

Czy możesz zwrócić każdy indeks, od którego zaczyna się permutacja s1 w s2, nadal w czasie O(m + n)?

Podpowiedzi

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

Otwarte: 0 z 3

Rozwiązanie

Wypisywanie permutacji s1 nie ma sensu: 10 liter daje już 3 628 800 uporządkowań. Rozwiązaniem jest przestać przejmować się kolejnością. Podciąg s2 jest permutacją s1 dokładnie wtedy, gdy ma taką samą długość m i taką samą liczbę wystąpień każdej litery. Każdy kandydat jest więc oknem o tej samej, ustalonej długości, które możesz przesuwać po s2, aktualizując liczniki liter: na każdym kroku dodajesz jedną literę i usuwasz jedną.

Policz każde okno od początku

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

Intuicja

Bezpośrednie podejście — zbudowanie każdej permutacji s1 i wyszukanie jej — od razu zawodzi: 20 liter ma ponad 2 × 10^18 możliwych uporządkowań. Zamiast tego odwróćmy pytanie. Podciąg znaków s2 jest permutacją s1, gdy zawiera dokładnie m liter i każda litera występuje w nim tyle razy, co w s1. Kolejność liter nie ma znaczenia.

Policz więc raz litery s1 w tabeli złożonej z 26 liczb: indeks 0 odpowiada a, a indeks 25 — z. Następnie weź każdy podciąg znaków s2 o długości m, policz jego litery w nowej tabeli i porównaj obie tabele. Dla tar w smartphone kolejne okna to sma, mar, art i tak dalej, a art pasuje: jedna litera a, jedna r i jedna t.

To rozwiązanie jest poprawne, bo sprawdza każdego kandydata. Jest powolne, ponieważ sąsiednie okna mają wspólne m-1 liter, a ty zliczasz je wszystkie od nowa. Dla m = 15,000 i n = 50,000 istnieje 35,001 okien, każde o długości 15,000 liter, co daje około 5 × 10^8 kroków.

Algorytm

Jeśli s1 jest dłuższe niż s2, zwróć false.
Policz litery s1 w tablicy need składającej się z 26 zer.
Dla każdego indeksu początkowego od 0 do n-m policz litery m znaków zaczynających się od tego indeksu w nowej tablicy.
Jeśli ta tablica jest równa need, zwróć true.
Po ostatnim oknie zwróć false.

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 False

Przesuwaj okno i porównuj liczby 26

Intuicja

Dwa sąsiednie okna różnią się tylko dwiema literami. Przejście od mar do art usuwa m z lewej strony i dodaje t z prawej. Dlatego przechowuj jedną tablicę dla bieżącego okna i aktualizuj ją w każdym kroku o jedno +1 i jedno -1, zamiast ponownie zliczać m liter.

Wypełnij need na podstawie s1, a window na podstawie pierwszych m liter z s2, a następnie porównaj je. Potem dla każdego i od m do n-1 dodaj s2[i], usuń s2[i-m] i ponownie je porównaj. Okno obejmuje teraz s2[i-m+1..i] i nadal ma m liter.

Każdy krok wymaga dwóch aktualizacji i porównania 26 liczb, niezależnie od wartości m. Dla największego wejścia to około 26 × 50,000 = 1.3 × 10^6 operacji, czyli złożoność liniowa względem długości s2. Tego rozwiązania oczekuje większość osób przeprowadzających rozmowy kwalifikacyjne.

Algorytm

Jeśli s1 jest dłuższy niż s2, zwróć false.
Policz znaki s1 w need, a pierwsze m liter s2 w window.
Jeśli obie tablice są równe, zwróć true.
Dla każdego i od m do n-1: dodaj 1 dla s2[i], odejmij 1 dla s2[i-m] i zwróć true, jeśli tablice są równe.
Zwróć false.

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 False

Przesuwaj okno i śledź niezrównoważone litery

Intuicja

Porównywanie 26 liczb na każdym kroku powtarza pracę, ponieważ w jednym kroku zmieniają się tylko dwie z nich. Zamiast tego przechowuj jedną tablicę balance: balance[c] to liczba wystąpień litery c w s1 pomniejszona o liczbę jej wystąpień w oknie. Okno jest permutacją s1 dokładnie wtedy, gdy wszystkie 26 wartości w tablicy wynosi 0. Obok tablicy przechowuj unbalanced — liczbę liter, których wartość w tablicy nie wynosi 0 — i zwróć true, gdy tylko ta wartość osiągnie 0.

Ta metoda wymaga jednej zasady. Zanim zmienisz balance[c], sprawdź, czy jego wartość wynosi 0. Jeśli tak, litera zaraz straci równowagę, więc zwiększ unbalanced o 1. Po zmianie sprawdź, czy jego wartość wynosi 0. Jeśli tak, litera odzyskała równowagę, więc zmniejsz unbalanced o 1. Litera wchodząca do okna zmniejsza swoją wartość w tablicy o 1, a litera opuszczająca okno zwiększa ją o 1. Zmiana wartości z 2 na 1 nie uruchamia żadnego sprawdzenia, i słusznie: litera nie miała równowagi i nadal jej nie ma.

Prześledźmy tar i smartphone. Początkowe wartości wynoszą: a: 1, r: 1, t: 1, więc unbalanced wynosi 3. Litery s i m wchodzą do okna, zwiększając tę wartość do 5, a potem wchodzi a, której wartość spada do 0: unbalanced wynosi teraz 4. Wchodzi r (3), a s opuszcza okno (2). Wchodzi t (1), a m opuszcza okno (0), więc okno art jest odpowiedzią.

Możesz sprawdzać, czy unbalanced == 0, już od pierwszej litery. Gdy w oknie jest mniej niż m liter, suma wartości w tablicy jest dodatnia, więc co najmniej jedna z nich nie wynosi 0. Każdy krok wymaga stałej ilości pracy, więc całe przeszukiwanie zajmuje O(m + n), a tablica zawsze zawiera 26 liczb, więc wymaga O(1) pamięci.

Algorytm

Jeśli s1 jest dłuższy niż s2, zwróć false.
Zlicz znaki z s1 w balance i ustaw unbalanced na liczbę liter, których saldo jest różne od 0.
Dla każdego indeksu i w s2 odejmij 1 od salda znaku s2[i], zwiększając unbalanced o 1, jeśli to saldo wynosiło 0, i zmniejszając je o 1, jeśli saldo stanie się równe 0.
Jeśli i ≥ m, zwiększ saldo znaku s2[i-m] o 1, wykonując te same aktualizacje.
Jeśli unbalanced wynosi 0, zwróć true. Po pętli zwróć false.

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

Pułapki i przypadki brzegowe

Większość błędnych odpowiedzi wynika z nieprawidłowego traktowania brzegów okna albo sprawdzania, które litery się w nim pojawiają, zamiast tego, ile razy występują.

Sprawdzanie tylko, czy każda litera z s1 znajduje się w oknie. onio zawiera wszystkie litery z noon, ale nie jest jego permutacją. Porównaj liczebności.
Usuwanie niewłaściwej litery. Gdy s2[i] wchodzi do okna, opuszcza je litera s2[i-m], więc okno staje się równe s2[i-m+1..i]. Usunięcie s2[i-m+1] pozostawia okno złożone z m-1 liter.
Pominięcie pierwszego okna. Jeśli porównujesz dopiero po przesunięciu okna, permutacja na indeksie 0 nigdy nie zostanie znaleziona.
Nieuwzględnienie przypadku, w którym s1 jest dłuższe niż s2. W Rust operacja n - m na długościach bez znaku powoduje niedomiar, a w Swift zakres 0...(n - m) wywołuje błąd. Najpierw zwróć false.
Porównywanie tablic za pomocą == w języku, w którym porównywane są ich referencje. W JavaScript i Dart dwie różne tablice nigdy nie są równe za pomocą ==; w Java użyj Arrays.equals.

Najczęstsze pytania4

Jaka jest złożoność czasowa Permutation in String?

W przypadku okna przesuwnego złożoność wynosi O(m + n), gdzie m to długość s1, a n to długość s2. Zliczasz s1 raz, a następnie każda litera s2 raz wchodzi do okna i raz je opuszcza. Ponowne zliczanie każdego okna od początku kosztuje natomiast O(n · m).

Czy problem „Permutation in String” polega na znalezieniu anagramu w ciągu znaków?

Tak. Permutacja s1 jest jego anagramem, więc pytanie brzmi, czy jakiś podciąg s2 o długości m jest anagramem s1. Sprawdzenie, czy dwa całe ciągi znaków są anagramami, polega na jednorazowym porównaniu liczby wystąpień liter; tutaj to samo porównanie wykonuje się dla okna przesuwającego się wzdłuż s2.

Dlaczego przesuwane okno ma tutaj stały rozmiar?

Każda permutacja s1 ma dokładnie m liter, więc dopasować mogą się tylko okna o długości m. W problemach takich jak znalezienie najdłuższego podciągu bez powtórzeń okno się powiększa i zmniejsza; tutaj oba jego brzegi przesuwają się razem, po jednym kroku.

Czy mogę użyć mapy haszującej zamiast tablicy z 26 licznikami?

Tak, i potrzebujesz jej, jeśli ciągi znaków mogą zawierać dowolne znaki. Jeśli zawierają tylko małe litery, tablica o rozmiarze 26 jest szybsza i zajmuje stałą ilość pamięci. W przypadku mapy usuwaj klucz, gdy jego licznik spadnie do 0, aby dwie mapy zawierające te same litery były uznawane za równe, albo zachowaj licznik unbalanced z poprzedniego podejścia, który działa tak samo z mapą.

Python

def checkInclusion(s1, s2):
    # Wpisz kod tutaj

Przypadki testowe

Przypadek 1

Przypadek 2

Przypadek 3

Wejście

s1 = "tar"
s2 = "smartphone"

Oczekiwane

true

Permutation in String

Funkcja

Ograniczenia

Przykłady

Podpowiedzi

Rozwiązanie

Policz każde okno od początku

Przesuwaj okno i porównuj liczby 26

Przesuwaj okno i śledź niezrównoważone litery

Pułapki i przypadki brzegowe

Najczęstsze pytania4

Podobne zadania