Decode Ways

Q: Wie geht man bei „Decode Ways“ mit Nullen um?

Eine 0 ist niemals allein ein Buchstabe, also muss sie sich mit der Ziffer davor zu 10 oder 20 verbinden. Sie addiert die Anzahl von zwei Ziffern zuvor nur nach einer 1 oder einer 2 und andernfalls nichts. Eine führende 0 , zwei Nullen hintereinander oder eine 0 nach einer 3 bis 9 ergibt 0.

MittelDynamische Programmierung

+10

Eine Nachricht aus Großbuchstaben wurde mit A = 1, B = 2 und so weiter bis Z = 26 codiert, und die Codes wurden ohne Trennzeichen geschrieben. Gegeben sei die Ziffernfolge s. Gib zurück, wie viele Nachrichten sie erzeugt haben könnten.

Ein Buchstabe wird aus einer einzelnen Ziffer oder zwei benachbarten Ziffern gelesen, und ein Code beginnt nie mit 0: 06 ist nicht 6, und eine einzelne 0 ist kein Buchstabe. Wenn keine Lesart funktioniert, gib 0 zurück.

Funktion

numDecodings(s: string) → integer

sstring: die Ziffernfolge zum Dekodieren
Gibt zurückinteger: die Anzahl der Buchstaben-Nachrichten, die zu s codieren

Einschränkungen

1 ≤ s.length ≤ 100
s enthält nur die Ziffern 0 bis 9 und kann mit 0 beginnen.
Jedes Präfix und jedes Suffix von s hat weniger als 2³¹ Lesarten, daher passen die Antwort und alle Zählwerte, die du unterwegs ermittelst, in eine vorzeichenbehaftete 32-Bit-Ganzzahl.

Beispiele

Eingabe: s = "2611"
Ausgabe: 4
Erklärung: Die vier Lesarten sind 2 6 1 1 (BFAA), 26 1 1 (ZAA), 2 6 11 (BFK) und 26 11 (ZK). Die mittleren Ziffern bilden nie ein Paar, weil 61 größer als 26 ist.

Eingabe: s = "1203"
Ausgabe: 1
Erklärung: Die 0 muss sich mit der vorhergehenden 2 zu 20 verbinden, wodurch 1 20 3 (ATC) erzwungen wird. Würde man zuerst 12 lesen, bliebe die 0 allein, und 03 beginnt mit 0.

Eingabe: s = "06"
Ausgabe: 0
Erklärung: Der erste Buchstabe müsste mit 0 beginnen. Eine einzelne 0 ist kein Buchstabe und 06 ist kein Code, daher ergibt keine Nachricht diese Zeichenfolge.

Weiterführende Frage

Was ist, wenn s auch * enthalten kann, das für eine beliebige Ziffer von 1 bis 9 steht? Kannst du die Anzahl der Lesarten in O(n) Zeit modulo 10^9+7 zählen?

Tipps

Öffne sie nacheinander. Jeder verrät ein bisschen mehr.

0 von 3 geöffnet

Lösung

Jede Ziffer ist entweder ein einzelner Buchstabe oder verbindet sich mit ihrem Nachbarn, sodass die Anzahl der Lesarten wie die Fibonacci-Zahlen wächst: 45 Einsen ergeben 1836311903. Sie aufzulisten ist aussichtslos, aber die Möglichkeiten, eine Lesart zu vervollständigen, hängen nur von der erreichten Position ab, sodass jede Position nur einmal gezählt werden muss. Eine 0 kann nur 10 oder 20 abschließen.

Probiere beide Lesarten mit Rekursion aus

Korrekt, wird aber bei den größten Tests nicht fertig

Idee

Am Index i beginnt eine 0 keinen Buchstaben, daher ergibt der Pfad keine Lesarten. Andernfalls lies eine Ziffer und zähle den Rest ab i+1; bilden die beiden Ziffern eine Zahl von 10 bis 26, lies auch beide und zähle ab i+2. Die beiden Möglichkeiten ergeben unterschiedliche erste Buchstaben, daher addieren sich ihre Anzahlen ohne Überschneidung, und wenn das Ende erreicht ist, ist eine Lesart vollständig.

Es wird nichts gespeichert, daher folgen die Aufrufe der Fibonacci-Regel: 45 Einsen erfordern etwa 5 × 10^9 Aufrufe. Eine Antwort von 0 ist nicht schneller: 44 Einsen, 55 Dreien und eine abschließende 0 erfordern etwa 10^11 Aufrufe, da jede Lesart der Einsen erst an der letzten Ziffer scheitert.

Algorithmus

waysFrom(i) zählt die möglichen Lesarten der Ziffern ab Index i.
Am Ende der Zeichenfolge gib 1 zurück. Bei einer 0 gib 0 zurück.
Andernfalls gib waysFrom(i+1) zurück, plus waysFrom(i+2), wenn die Ziffern an den Indizes i und i+1 eine Zahl von höchstens 26 bilden.
Die Antwort ist 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)

Rekursion mit Memoisierung

Idee

Die Rekursion stellt viele Male dieselbe Frage. Bei "11111" wird die Anzahl ab Index 3 nach 1 1 1, nach 11 1 und nach 1 11 benötigt, und sie ist jedes Mal gleich, weil sie nur von den Ziffern ab Index 3 abhängt. Speichere jede Anzahl beim ersten Berechnen und markiere noch nicht berechnete Plätze mit -1, da 0 eine gültige Anzahl ist.

Es gibt n Positionen, die jeweils einmal mit konstantem Aufwand berechnet werden: Laufzeit O(n). Das Memo und der Aufrufstapel benötigen O(n) Speicherplatz, bei höchstens 100 Aufrufen Tiefe.

Algorithmus

Fülle memo mit -1, ein Eintrag pro Index.
Gib in waysFrom(i) am Ende der Zeichenfolge 1 zurück und memo[i], wenn es nicht -1 ist.
Zähle andernfalls wie bei der einfachen Rekursion, speichere die Anzahl in memo[i] (auch wenn sie null ist) und gib sie zurück.

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)

Bottom-up mit zwei Zählern

Idee

Zähle stattdessen Präfixe. Sei ways(i) die Anzahl der Lesarten der ersten i Ziffern. Der letzte Buchstabe ist entweder die Ziffer i-1 allein, wofür sie zwischen 1 und 9 liegen muss und die ways(i-1) Lesarten übrig lässt, oder die Ziffern i-2 und i-1 zusammen, die eine Zahl zwischen 10 und 26 ergeben müssen und ways(i-2) übrig lassen. Addiere die Anzahlen, deren Bedingung erfüllt ist. Das leere Präfix hat eine Lesart, also gilt ways(0) = 1.

Bei "1203" entwickeln sich die Anzahlen zu 1, 2 und fallen dann bei der 0 wieder auf 1 zurück, weil nur 20 funktioniert und die Anzahl vor der 2 übrig lässt. Die 3 steht für sich allein, daher bleibt die Anzahl bei 1. Jede Anzahl greift auf den Wert zwei Stellen zurück zu, daher ersetzen zwei Variablen die Tabelle: O(n) Zeit, O(1) Speicher.

Algorithmus

Setze twoBack = 0 und oneBack = 1, die Anzahl für das leere Präfix.
Setze für jeden Index i current auf oneBack, wenn Ziffer i nicht 0 ist, andernfalls auf 0.
Wenn i ≥ 1 gilt, Ziffer i-1 nicht 0 ist und die Ziffern i-1 und i zusammen höchstens 26 ergeben, addiere twoBack.
Verschiebe: twoBack = oneBack, dann oneBack = current.
Gib oneBack zurück.

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

Stolperfallen und Grenzfälle

0 als Buchstaben zu behandeln oder 06 als 6. "30", "100" und "06" haben alle 0 Lesarten.
Ein zweistelliges Teilstück nur mit ≤ 26 zu testen. 05 ist als Zahl 5, aber kein Code. Prüfe daher, dass die erste Ziffer nicht 0 ist.
Unbekannte Memo-Speicherplätze mit 0 zu markieren. Positionen mit 0 Lesarten gelten dann nie als gespeichert: Bei 44 Einsen, 55 Dreien und einer abschließenden 0 bist du wieder bei etwa 10^11 Aufrufen.
Die Ziffer vor Index 0 zu lesen. Sichere die Prüfung auf zwei Ziffern mit i ≥ 1 ab; in Python liest s[-1] unbemerkt die letzte Ziffer.
s in eine Zahl umzuwandeln. Hundert Ziffern passen in keinen Ganzzahltyp, und die führenden Nullen, die das Ergebnis verändern, gehen verloren.

Häufige Fragen3

Wie hoch ist die Zeitkomplexität von Decode Ways?

Die Bottom-up-Lösung liest jede Ziffer genau einmal mit konstantem Aufwand: O(n) Zeit und O(1) zusätzlichen Speicherplatz. Memoisierte Rekursion benötigt ebenfalls O(n) Zeit, aber O(n) Speicherplatz. Einfache Rekursion hat exponentielle Laufzeit: Bei einer Zeichenkette aus Einsen wächst die Anzahl der Aufrufe etwa wie 1.618^n.

Wie hängt Decode Ways mit Climbing Stairs zusammen?

Beide zählen die Möglichkeiten, eine Linie mit Schritten der Länge 1 und 2 abzudecken. Bei „Climbing Stairs“ ist jeder Schritt erlaubt, daher entsprechen die Anzahlen den Fibonacci-Zahlen. Bei „Decode Ways“ muss ein Schritt mit einer Ziffer zwischen 1 und 9 und ein Schritt mit zwei Ziffern zwischen 10 und 26 liegen. Daher wird jeder Term nur addiert, wenn seine Bedingung erfüllt ist.

Wie geht man bei „Decode Ways“ mit Nullen um?

Eine 0 ist niemals allein ein Buchstabe, also muss sie sich mit der Ziffer davor zu 10 oder 20 verbinden. Sie addiert die Anzahl von zwei Ziffern zuvor nur nach einer 1 oder einer 2 und andernfalls nichts. Eine führende 0, zwei Nullen hintereinander oder eine 0 nach einer 3 bis 9 ergibt 0.

def numDecodings(s):
    # Schreibe hier den Code

Test #1

Test #2

Test #3

Argument

s = "2611"

Erwartete Ausgabe

Decode Ways

Funktion

Einschränkungen

Beispiele

Tipps

Lösung

Probiere beide Lesarten mit Rekursion aus

Rekursion mit Memoisierung

Bottom-up mit zwei Zählern

Stolperfallen und Grenzfälle

Häufige Fragen3

Ähnliche Aufgaben