Decode Ways

Q: Jak obsługiwać zera w problemie Decode Ways?

0 nigdy nie jest samodzielną literą, więc musi łączyć się z poprzedzającą go cyfrą, tworząc 10 lub 20 . Dodaje liczbę sposobów sprzed dwóch cyfr tylko po 1 lub 2 , a w pozostałych przypadkach nic. Początkowe 0 , dwa zera z rzędu lub 0 po cyfrze od 3 do 9 dają 0.

ŚrednieProgramowanie dynamiczne

+10

Wiadomość składającą się z wielkich liter zakodowano za pomocą A = 1, B = 2 itd. aż do Z = 26, a kody zapisano bez separatorów. Mając ciąg cyfr s, zwróć liczbę wiadomości, które mogły go utworzyć.

Literę odczytuje się z jednej cyfry lub dwóch sąsiadujących cyfr, a kod nigdy nie zaczyna się od 0: 06 to nie 6, a samotne 0 nie jest literą. Jeśli żaden odczyt nie jest możliwy, zwróć 0.

Funkcja

numDecodings(s: string) → integer

sstring: ciąg cyfr do zdekodowania
Zwracainteger: liczba wiadomości literowych, które kodują się na s

Ograniczenia

1 ≤ s.length ≤ 100
s zawiera wyłącznie cyfry od 0 do 9 i może zaczynać się od 0.
Każdy prefiks i każdy sufiks s ma mniej niż 2³¹ odczytów, więc odpowiedź i każda liczba, którą obliczysz po drodze, mieszczą się w 32-bitowej liczbie całkowitej ze znakiem.

Przykłady

Wejście: s = "2611"
Wyjście: 4
Wyjaśnienie: Cztery odczyty to 2 6 1 1 (BFAA), 26 1 1 (ZAA), 2 6 11 (BFK) i 26 11 (ZK). Środkowe cyfry nigdy nie tworzą pary, ponieważ 61 jest większe niż 26.

Wejście: s = "1203"
Wyjście: 1
Wyjaśnienie: 0 musi połączyć się z poprzedzającą je 2 w 20, co wymusza 1 20 3 (ATC). Odczytanie najpierw 12 pozostawiłoby 0 bez pary, a 03 zaczyna się od 0.

Wejście: s = "06"
Wyjście: 0
Wyjaśnienie: Pierwsza litera musiałaby zaczynać się od 0. Samo 0 nie jest literą, a 06 nie jest kodem, więc żadna wiadomość nie daje tego ciągu.

Pytanie dodatkowe

Co jeśli s może również zawierać *, oznaczającą dowolną cyfrę od 1 do 9? Czy potrafisz policzyć liczbę możliwych odczytów w czasie O(n), modulo 10^9+7?

Podpowiedzi

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

Otwarte: 0 z 3

Rozwiązanie

Każda cyfra jest osobną literą albo łączy się z sąsiednią, więc liczba odczytów rośnie jak liczby Fibonacciego: 45 jedynek daje 1836311903 odczyty. Wypisanie ich wszystkich jest beznadziejne, ale sposoby dokończenia odczytu zależą tylko od osiągniętej pozycji, więc każdą pozycję trzeba policzyć tylko raz. 0 może być tylko końcem 10 lub 20.

Wypróbuj oba odczyty z rekurencją

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

Intuicja

Na indeksie i cyfra 0 nie rozpoczyna żadnej litery, więc ta ścieżka nie daje żadnego odczytu. W przeciwnym razie odczytaj jedną cyfrę i policz pozostałe od i+1; jeśli te dwie cyfry tworzą liczbę od 10 do 26, odczytaj także obie i policz od i+2. Te dwa wybory dają różne pierwsze litery, więc ich liczby można dodać bez nakładania się, a dotarcie do końca oznacza jeden kompletny odczyt.

Nic nie jest zapamiętywane, więc wywołania podlegają regule Fibonacciego: 45 jedynek wymaga około 5 × 10^9 wywołań. Odpowiedź 0 nie jest szybsza: 44 jedynki, 55 trójek i końcowe 0 wymagają około 10^11 wywołań, ponieważ każdy odczyt jedynek kończy się niepowodzeniem dopiero na ostatniej cyfrze.

Algorytm

waysFrom(i) zlicza możliwości odczytania cyfr od indeksu i dalej.
Na końcu ciągu zwróć 1. Dla 0 zwróć 0.
W przeciwnym razie zwróć waysFrom(i+1) oraz waysFrom(i+2), jeśli cyfry i i i+1 tworzą liczbę nie większą niż 26.
Odpowiedzią jest waysFrom(0).

def numDecodings(s):
    n = len(s)

    def ways_from(i):
        # The number of ways to decode s[i:].
        if i == n:
            return 1  # nothing left: one finished reading
        if s[i] == "0":
            return 0  # no letter code starts with 0
        ways = ways_from(i + 1)  # read one digit
        if i + 1 < n and int(s[i:i + 2]) <= 26:
            ways += ways_from(i + 2)  # read two digits, 10 to 26
        return ways

    return ways_from(0)

Rekurencja z memoizacją

Intuicja

Rekurencja zadaje to samo pytanie wiele razy. W przypadku "11111" liczba dla indeksu 3 jest potrzebna po 1 1 1, po 11 1 i po 1 11, a za każdym razem jest taka sama, ponieważ zależy tylko od cyfr od indeksu 3 wzwyż. Zapisz każdą liczbę przy jej pierwszym obliczeniu i oznacz nieobliczone jeszcze miejsca wartością -1, ponieważ 0 jest rzeczywistą liczbą.

Jest n pozycji, a każda jest obliczana raz przy stałym nakładzie pracy: czas O(n). Memo i stos wywołań zajmują O(n) pamięci, przy maksymalnej głębokości 100 wywołań.

Algorytm

Wypełnij memo wartością -1, po jednym miejscu na każdy indeks.
W waysFrom(i) zwróć 1 na końcu ciągu i memo[i], jeśli nie jest równe -1.
W przeciwnym razie zliczaj tak jak w zwykłej rekurencji, zapisz wynik w memo[i], również gdy wynosi zero, i zwróć go.

def numDecodings(s):
    n = len(s)
    memo = [-1] * n  # memo[i]: ways to decode s[i:], -1 until worked out

    def ways_from(i):
        if i == n:
            return 1
        if memo[i] != -1:
            return memo[i]
        ways = 0
        if s[i] != "0":
            ways = ways_from(i + 1)  # read one digit
            if i + 1 < n and int(s[i:i + 2]) <= 26:
                ways += ways_from(i + 2)  # read two digits, 10 to 26
        memo[i] = ways
        return ways

    return ways_from(0)

Oddolnie z dwoma licznikami

Intuicja

Zamiast tego zliczaj prefiksy. Niech ways(i) oznacza liczbę odczytów pierwszych i cyfr. Ostatnią literą jest albo sama cyfra i-1, która musi być z zakresu od 1 do 9 i pozostawia ways(i-1) odczytów, albo razem cyfry i-2 i i-1, które muszą utworzyć liczbę od 10 do 26 i pozostawiają ways(i-2). Dodaj części, których warunek jest spełniony. Pusty prefiks ma jeden odczyt, więc ways(0) = 1.

Dla "1203" liczby wynoszą 1, 2, a potem z powrotem 1 przy 0, ponieważ działa tylko 20 i pozostawia liczbę sprzed 2. 3 występuje samodzielnie, więc liczba pozostaje równa 1. Każda liczba odwołuje się do tej sprzed dwóch pozycji, więc tabelę zastępują dwie zmienne: czas O(n), pamięć O(1).

Algorytm

Ustaw twoBack = 0 i oneBack = 1 — liczby dla pustego prefiksu.
Dla każdego indeksu i ustaw current na oneBack, jeśli cyfra i nie jest równa 0, a w przeciwnym razie na 0.
Jeśli i ≥ 1, cyfra i-1 nie jest równa 0, a cyfry i-1 i i tworzą liczbę nie większą niż 26, dodaj twoBack.
Przesuń: twoBack = oneBack, a następnie oneBack = current.
Zwróć oneBack.

def numDecodings(s):
    # ways(i) counts the readings of the first i digits; ways(0) = 1.
    two_back, one_back = 0, 1  # ways(i-1) and ways(i) before digit i is read
    for i in range(len(s)):
        current = 0
        if s[i] != "0":
            current = one_back  # digit i is a letter on its own
        if i >= 1 and s[i - 1] != "0" and int(s[i - 1:i + 1]) <= 26:
            current += two_back  # digits i-1 and i form one letter, 10 to 26
        two_back, one_back = one_back, current
    return one_back

Pułapki i przypadki brzegowe

Traktowanie 0 jak litery lub 06 jak liczby 6. "30", "100" i "06" mają po 0 odczytów.
Sprawdzanie dwucyfrowego fragmentu wyłącznie za pomocą ≤ 26. 05 to liczba 5, ale nie kod, więc sprawdź, czy jej pierwsza cyfra nie jest równa 0.
Oznaczanie nieznanych miejsc w pamięci podręcznej wartością 0. Pozycje z 0 odczytami nigdy nie są uznawane za zapisane: przy 44 jedynkach, 55 trójkach i końcowym 0 wracasz do około 10^11 wywołań.
Odczytywanie cyfry przed indeksem 0. Zabezpiecz sprawdzanie dwóch cyfr warunkiem i ≥ 1; w Pythonie s[-1] po cichu odczytuje ostatnią cyfrę.
Konwertowanie s na jedną liczbę. Sto cyfr nie mieści się w żadnym typie całkowitoliczbowym, a zera wiodące, które zmieniają odpowiedź, zostają utracone.

Najczęstsze pytania3

Jaka jest złożoność czasowa problemu Decode Ways?

Rozwiązanie budowane od dołu odczytuje każdą cyfrę raz, wykonując stałą ilość pracy: czas O(n) i dodatkowa przestrzeń O(1). Rekurencja z memoizacją również zajmuje O(n) czasu, ale wymaga O(n) przestrzeni. Zwykła rekurencja ma złożoność wykładniczą: dla ciągu jedynek liczba wywołań rośnie jak 1.618^n.

Jaki jest związek między Decode Ways a Climbing Stairs?

W obu przypadkach liczy się sposoby pokrycia odcinka krokami o długości 1 i 2. W Climbing Stairs dozwolony jest każdy krok, więc liczby sposobów są liczbami Fibonacciego. W Decode Ways krok o długości jednej cyfry wymaga wartości od 1 do 9, a krok o długości dwóch cyfr — od 10 do 26, więc każdy wyraz jest dodawany tylko wtedy, gdy spełniony jest jego warunek.

Jak obsługiwać zera w problemie Decode Ways?

0 nigdy nie jest samodzielną literą, więc musi łączyć się z poprzedzającą go cyfrą, tworząc 10 lub 20. Dodaje liczbę sposobów sprzed dwóch cyfr tylko po 1 lub 2, a w pozostałych przypadkach nic. Początkowe 0, dwa zera z rzędu lub 0 po cyfrze od 3 do 9 dają 0.

def numDecodings(s):
    # Wpisz kod tutaj

Test #1

Test #2

Test #3

Argument

s = "2611"

Oczekiwany wynik

Decode Ways

Funkcja

Ograniczenia

Przykłady

Podpowiedzi

Rozwiązanie

Wypróbuj oba odczyty z rekurencją

Rekurencja z memoizacją

Oddolnie z dwoma licznikami

Pułapki i przypadki brzegowe

Najczęstsze pytania3

Podobne zadania