Decode Ways

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

0 nigdy nie może być samodzielną literą, więc musi być połączone z poprzedzającą je cyfrą, a kodami są tylko 10 i 20 . W pętli od dołu do góry oznacza to, że 0 nic nie dodaje w przypadku jednej cyfry, a liczbę sposobów sprzed dwóch cyfr dodaje tylko po cyfrze 1 lub 2. Początkowe 0 , dwa zera z rzędu lub 0 po cyfrze od 3 do 9 sprawiają, że wynik wynosi 0.

ŚrednieProgramowanie dynamiczne

+10

Wiadomość zapisana wielkimi literami została zamieniona na cyfry za pomocą kodu A = 1, B = 2 i tak dalej aż do Z = 26, a kody zapisano jeden po drugim, bez separatorów. Otrzymujesz ciąg cyfr s. Zwróć liczbę różnych wiadomości, które mogły go utworzyć.

Każdą literę odczytuje się z jednej cyfry albo z dwóch sąsiadujących ze sobą cyfr, a kod nigdy nie zaczyna się od 0: 06 to nie 6, a samo 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 składających się z liter, 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ą ją 2, tworząc 20, co wymusza odczyt 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.

+25 ukrytych testów przy wysłaniu

Pytanie dodatkowe

A co, jeśli s może również zawierać *, który oznacza dowolną cyfrę od 1 do 9? Czy potrafisz policzyć odczyty w czasie O(n), zwracając wynik modulo 10^9+7?

Podpowiedzi

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

Otwarte: 0 z 3

Rozwiązanie

Każda cyfra albo jest samodzielną literą, albo łączy się z sąsiednią, tworząc dwucyfrową literę, więc liczba odczytów rośnie jak liczby Fibonacciego: 45 jedynek ma ich już 1836311903. Wypisanie wszystkich odczytów jest beznadziejne. Problem można rozwiązać, zauważając, że liczba sposobów dokończenia odczytu zależy tylko od osiągniętej pozycji, więc każdą pozycję trzeba policzyć raz. To przy zerach trzeba zachować ostrożność: 0 może być tylko drugą cyfrą w 10 lub 20.

Wypróbuj oba odczyty rekurencyjnie

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

Intuicja

Stań na indeksie i i spójrz na następną cyfrę. Jeśli to 0, żadna litera się tutaj nie zaczyna i ta ścieżka nie daje żadnych odczytów. W przeciwnym razie możesz odczytać tę cyfrę jako jedną literę i zliczyć odczyty pozostałej części od i+1. Jeśli wraz z następną cyfrą tworzy liczbę od 10 do 26, możesz też odczytać obie cyfry jako jedną literę i zliczyć odczyty od i+2. Te dwa wybory dają różne pierwsze litery, więc ich liczby sumują się bez nakładania. Gdy i dotrze do końca ciągu, masz za sobą jeden kompletny odczyt, więc zwracasz 1.

Dla "2611": pierwszą literą jest 2 albo 26. Po 2 następna litera musi być 6, ponieważ 61 jest za duże. Obie gałęzie kończą się potem na 1 1 albo 11, więc łączna liczba wynosi 2 × 2 = 4.

Wynik jest poprawny, ale nic nie zostaje zapamiętane. W ciągu złożonym z jedynek każde wywołanie rozgałęzia się na dwie ścieżki, a wywołania podlegają regule Fibonacciego, więc przetworzenie 45 jedynek wymaga około 5 × 10^9 wywołań. Nakład pracy nie maleje też wraz z wynikiem: dla 44 jedynek, po których następuje 55 trójek i końcowe 0, wynik wynosi 0, a mimo to rekurencja przechodzi przez każdy odczyt jedynek i wszystkie trójki, zanim każda ścieżka zakończy się na ostatniej cyfrze — to około 10^11 wywołań.

Algorytm

Napisz funkcję pomocniczą waysFrom(i), która zlicza możliwe odczytania cyfr od indeksu i do końca.
Jeśli i jest równe długości s, zwróć 1.
Jeśli cyfra na pozycji i to 0, zwróć 0.
Zacznij od waysFrom(i+1) — odczytań, w których następna litera odpowiada jednej cyfrze.
Jeśli cyfry i i i+1 tworzą liczbę nie większą niż 26, dodaj waysFrom(i+2). Zwróć 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 pamięcią podręczną

Intuicja

Rekurencja zadaje wciąż to samo pytanie. W ciągu "11111" wynik dla indeksu 3 jest potrzebny po 1 1 1, po 11 1 i po 1 11, a za każdym razem jest taki sam, ponieważ zależy tylko od cyfr od indeksu 3 wzwyż. Zapisz każdy wynik w tablicy memo za pierwszym razem, gdy go obliczysz, a później odczytuj go stamtąd.

Oznacz miejsca, których wyniku jeszcze nie obliczono, za pomocą -1, a nie 0. Zero jest tutaj prawidłowym wynikiem: w ciągu kończącym się na 30 każda pozycja ma 0 odczytów. Jeśli użyjesz 0 jako oznaczenia, te pozycje przy każdej wizycie będą wyglądać na nieznane, a rekurencja będzie równie powolna jak wcześniej.

Jest n pozycji, a wynik dla każdej z nich jest obliczany raz przy stałym nakładzie pracy, więc czas działania wynosi O(n). Tablica memo i stos wywołań zajmują po O(n) pamięci. Wywołania zagnieżdżają się tutaj na maksymalnie 100 poziomach, z czym radzi sobie każdy język.

Algorytm

Utwórz tablicę memo z jednym miejscem dla każdego indeksu, wszystkie ustawione na -1.
W waysFrom(i) zwróć 1 na końcu ciągu i memo[i], gdy jego wartość nie wynosi -1.
W przeciwnym razie zliczaj tak jak w zwykłej rekurencji: 0 dla 0, a w innym przypadku waysFrom(i+1) plus waysFrom(i+2), gdy dwie cyfry tworzą liczbę od 10 do 26.
Zapisz liczbę w memo[i], także gdy wynosi zero, i ją zwróć.
Zwróć waysFrom(0).

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

Odwróć rekurencję i zliczaj prefiksy. Niech ways(i) oznacza liczbę odczytań pierwszych i cyfr. Ostatnią literą takiego odczytania jest albo sama cyfra o indeksie i-1, która musi być cyfrą od 1 do 9 i pozostawia ways(i-1) odczytań pozostałej części, albo dwie cyfry o indeksach i-2 i i-1, które muszą tworzyć liczbę od 10 do 26 i pozostawiają ways(i-2) odczytań. Zatem ways(i) jest sumą tych części, których warunek jest spełniony. Pusty prefiks ma jedno odczytanie — pustą wiadomość — więc ways(0) = 1.

Przejdź przez "1203". Po 1 licznik wynosi 1. Po 12 wynosi 2: 1 2 i 12. 0 nie może występować samodzielnie, a działa tylko 20, więc licznik wraca do wartości sprzed 2, czyli 1. 3 może występować samodzielnie, a 03 nie jest kodem, więc licznik pozostaje równy 1.

Każdy licznik korzysta tylko z dwóch poprzednich wartości, więc dwie zmienne, twoBack i oneBack, zastępują tabelę. To jedno przejście ze stałą ilością pracy dla każdej cyfry: czas O(n), pamięć O(1) i brak rekurencji.

Algorytm

Ustaw twoBack = 0 i oneBack = 1 — liczbę dla pustego prefiksu.
Dla każdego indeksu i rozpocznij od ustawienia current na 0 i dodaj oneBack, jeśli cyfra i nie jest równa 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ń wartości: twoBack = oneBack, a następnie oneBack = current.
Po ostatniej cyfrze 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

Prawie każda błędna odpowiedź na to zadanie wynika z zer albo z pamięci podręcznej, która zapomina.

Traktowanie 0 jako litery lub 06 jako 6. Zero może jedynie kończyć 10 lub 20, więc "30", "100" i "06" mają po 0 odczytów.
Sprawdzanie dwucyfrowego fragmentu wyłącznie pod kątem ≤ 26. 05 to 5 jako liczba, ale nie jest kodem. Sprawdź, czy pierwsza z tych dwóch cyfr nie jest równa 0.
Używanie 0 jako oznaczenia niewyliczonego jeszcze miejsca w pamięci podręcznej. Wiele pozycji naprawdę ma 0 odczytów, więc te miejsca nigdy nie są uznawane za zapisane, a ich wartość jest obliczana ponownie przy każdej wizycie. Dla 44 jedynek, po których następują trójki i końcowe 0, każde miejsce ma wartość 0, a liczba wywołań znów wynosi około 10^11.
Odczytywanie cyfry przed indeksem 0. Zabezpiecz sprawdzanie dwóch cyfr warunkiem i ≥ 1: w Pythonie s[-1] po cichu odczytuje ostatnią cyfrę, a inne języki odczytują znak spoza ciągu.
Konwertowanie s na jedną liczbę. Stu cyfr nie da się zmieścić w żadnym typie całkowitym, a konwersja usuwa zera wiodące, które zmieniają odpowiedź. Przetwarzaj cyfry po jednej.
W Lua i R pozycje zaczynają się od 1, więc koniec ciągu znajduje się na pozycji n+1, a pierwsze sprawdzenie dwóch cyfr odbywa się na pozycji 2.

Najczęstsze pytania4

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

Rozwiązanie oddolne odczytuje każdą cyfrę tylko raz przy stałym nakładzie pracy, więc działa w czasie O(n) i wykorzystuje O(1) dodatkowej pamięci. Rekurencja z memoizacją również działa w czasie O(n), ale wykorzystuje O(n) pamięci na memoizację i stos wywołań. Zwykła rekurencja ma złożoność wykładniczą: dla ciągu jedynek liczba wywołań rośnie jak 1.618^n.

Jaki związek ma problem „Decode Ways” z problemem „Climbing Stairs”?

Oba zadania zliczają sposoby pokrycia odcinka krokami o długości 1 i 2. W Climbing Stairs dozwolony jest każdy krok, więc liczba sposobów jest liczbą Fibonacciego. W Decode Ways krok o długości jednej cyfry wymaga cyfry od 1 do 9, a krok o długości dwóch cyfr wymaga liczby od 10 do 26, dlatego każdy składnik sumy jest dodawany tylko wtedy, gdy spełniony jest jego warunek. Ciąg jedynek pozwala na każdy krok, a liczby sposobów są dokładnie liczbami Fibonacciego.

Jak obsługiwać zera w problemie Decode Ways?

0 nigdy nie może być samodzielną literą, więc musi być połączone z poprzedzającą je cyfrą, a kodami są tylko 10 i 20. W pętli od dołu do góry oznacza to, że 0 nic nie dodaje w przypadku jednej cyfry, a liczbę sposobów sprzed dwóch cyfr dodaje tylko po cyfrze 1 lub 2. Początkowe 0, dwa zera z rzędu lub 0 po cyfrze od 3 do 9 sprawiają, że wynik wynosi 0.

Czy problem Decode Ways można rozwiązać przy użyciu O(1) pamięci?

Tak. Liczba dla prefiksu zależy tylko od liczb dla dwóch prefiksów krótszych o jeden i dwa znaki, więc dwie zmienne zastępują całą tabelę. W każdym kroku obliczana jest nowa liczba na ich podstawie, a następnie przesuwa się je o jedną pozycję.

Python

def numDecodings(s):
    # Napisz kod tutaj

Przypadki testowe

Przypadek 1

Przypadek 2

Przypadek 3

Wejście

s = "2611"

Oczekiwane

Decode Ways

Funkcja

Ograniczenia

Przykłady

Podpowiedzi

Rozwiązanie

Wypróbuj oba odczyty rekurencyjnie

Rekurencja z pamięcią podręczną

Oddolnie z dwoma licznikami

Pułapki i przypadki brzegowe

Najczęstsze pytania4

Podobne zadania