Decode Ways

Q: Wie gehst du in „Decode Ways“ mit Nullen um?

Eine 0 kann niemals allein ein Buchstabe sein, daher muss sie mit der Ziffer davor ein Paar bilden, und nur 10 und 20 sind Codes. In der Bottom-up-Schleife bedeutet das, dass eine 0 im Fall einer einzelnen Ziffer nichts hinzufügt und den Zählerstand von zwei Stellen zuvor nur nach einer 1 oder einer 2 hinzufügt. Eine führende 0 , zwei Nullen hintereinander oder eine 0 nach einer Ziffer von 3 bis 9 ergibt als Antwort 0.

MittelDynamische Programmierung

+10

Eine Nachricht aus Großbuchstaben wurde mit dem Code A = 1, B = 2 usw. bis zu Z = 26 in Ziffern umgewandelt, und die Codes wurden ohne Trennzeichen hintereinander geschrieben. Du erhältst die Ziffernfolge s. Gib zurück, wie viele verschiedene Nachrichten daraus entstanden sein könnten.

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

Funktion

numDecodings(s: string) → integer

sstring: die zu dekodierende Ziffernfolge
Gibt zurückinteger: die Anzahl der Buchstabennachrichten, 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 jede Anzahl, die du unterwegs berechnest, 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 mit der davorstehenden 2 zu 20 zusammengefasst werden, wodurch die Lesart 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.

+25 versteckte Tests beim Einreichen

Weiterführende Frage

Was wäre, wenn s auch * enthalten könnte, das für jede Ziffer von 1 bis 9 steht? Kannst du die Anzahl der Lesarten in O(n)-Zeit zählen und die Anzahl modulo 10^9+7 zurückgeben?

Tipps

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

0 von 3 geöffnet

Lösung

Jede Ziffer ist entweder selbst ein Buchstabe oder verbindet sich mit ihrem Nachbarn zu einem zweistelligen Buchstaben, sodass die Anzahl der Lesarten wie die Fibonacci-Zahlen wächst: 45 Einsen ergeben bereits 1836311903 Lesarten. Alle Lesarten aufzulisten ist aussichtslos. Der entscheidende Punkt ist, dass die Anzahl der Möglichkeiten, eine Lesart zu vervollständigen, nur von der erreichten Position abhängt, sodass jede Position nur einmal gezählt werden muss. Bei den Nullen ist besondere Vorsicht geboten: Eine 0 kann nur die zweite Ziffer von 10 oder 20 sein.

Probiere beide Lesarten mit Rekursion aus

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

Idee

Stell dich an Index i und betrachte die nächste Ziffer. Ist sie 0, beginnt hier kein Buchstabe, und dieser Pfad ergibt keine Lesarten. Andernfalls kannst du diese Ziffer als einen Buchstaben lesen und die Lesarten des Rests ab i+1 zählen. Ergibt sie zusammen mit der Ziffer danach eine Zahl von 10 bis 26, kannst du auch beide als einen Buchstaben lesen und ab i+2 zählen. Die beiden Möglichkeiten ergeben unterschiedliche erste Buchstaben, daher addieren sich ihre Anzahlen ohne Überschneidung. Wenn i das Ende der Zeichenfolge erreicht, hast du eine vollständige Lesart abgeschlossen und gibst daher 1 zurück.

Bei "2611": Der erste Buchstabe ist 2 oder 26. Auf 2 muss der nächste Buchstabe 6 sein, denn 61 ist zu groß. Beide Zweige enden dann mit 1 1 oder 11, also beträgt die Summe 2 × 2 = 4.

Die Antwort ist richtig, aber nichts wird gespeichert. Bei einer Zeichenfolge aus Einsen verzweigt jeder Aufruf zweimal, und die Aufrufe folgen der Fibonacci-Regel, sodass 45 Einsen etwa 5 × 10^9 Aufrufe erfordern. Der Aufwand sinkt auch nicht mit der Antwort: Bei 44 Einsen, gefolgt von 55 Dreien und einer abschließenden 0, ist die Antwort 0, doch die Rekursion durchläuft jede Lesart der Einsen durch alle Dreien, bevor jeder Pfad an der letzten Ziffer endet — etwa 10^11 Aufrufe.

Algorithmus

Schreibe eine Hilfsfunktion waysFrom(i), die die Lesemöglichkeiten der Ziffern vom Index i bis zum Ende zählt.
Wenn i der Länge von s entspricht, gib 1 zurück.
Wenn die Ziffer an Position i 0 ist, gib 0 zurück.
Beginne mit waysFrom(i+1), den Lesemöglichkeiten, bei denen der nächste Buchstabe eine Ziffer belegt.
Wenn die Ziffern an den Positionen i und i+1 eine Zahl von höchstens 26 bilden, addiere waysFrom(i+2). Gib waysFrom(0) zurück.

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 einem Memo

Idee

Die Rekursion stellt immer wieder dieselbe Frage. In "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, denn sie hängt nur von den Ziffern ab Index 3 ab. Speichere jede Anzahl in einem Array memo, sobald du sie zum ersten Mal berechnet hast, und lies sie danach dort aus.

Markiere die noch nicht berechneten Plätze mit -1, nicht mit 0. Null ist hier eine gültige Antwort: In einer Zeichenfolge, die mit 30 endet, gibt es an jeder Position 0 Lesarten. Mit 0 als Markierung erscheinen diese Positionen bei jedem Aufruf unbekannt, und die Rekursion ist genauso langsam wie zuvor.

Es gibt n Positionen, und jede wird einmal mit konstantem Aufwand berechnet, daher beträgt die Laufzeit O(n). Das Memo und der Aufrufstapel benötigen jeweils O(n) Speicherplatz. Die Aufrufe sind hier höchstens 100 Ebenen tief verschachtelt, womit jede Sprache zurechtkommt.

Algorithmus

Erstelle ein Array memo mit einem Eintrag pro Index, alle auf -1 gesetzt.
Gib in waysFrom(i) am Ende der Zeichenfolge 1 zurück und memo[i], wenn der Wert nicht -1 ist.
Zähle andernfalls wie bei der einfachen Rekursion: 0 bei einer 0, andernfalls waysFrom(i+1) plus waysFrom(i+2), wenn die beiden Ziffern eine Zahl von 10 bis 26 bilden.
Speichere die Anzahl in memo[i], auch wenn sie null ist, und gib sie zurück.
Gib waysFrom(0) 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

Drehe die Rekursion um und zähle Präfixe. Sei ways(i) die Anzahl der Lesarten der ersten i Ziffern. Der letzte Buchstabe einer solchen Lesart ist entweder die Ziffer am Index i-1 allein, wofür eine Ziffer von 1 bis 9 erforderlich ist und ways(i-1) Lesarten für den Rest übrig bleiben, oder die beiden Ziffern an i-2 und i-1, die zusammen eine Zahl von 10 bis 26 ergeben müssen und ways(i-2) Lesarten übrig lassen. Also ist ways(i) die Summe der Anteile, deren Bedingung erfüllt ist. Das leere Präfix hat eine Lesart, die leere Nachricht, also gilt ways(0) = 1.

Gehe "1203" durch. Nach 1 ist die Anzahl 1. Nach 12 ist sie 2: 1 2 und 12. Die 0 kann nicht allein stehen und nur 20 funktioniert, daher fällt die Anzahl auf den Wert vor der 2 zurück, also 1. Die 3 steht allein und 03 ist kein Code, daher bleibt die Anzahl bei 1.

Jede Anzahl betrachtet nur die beiden vorherigen Anzahlen, daher ersetzen zwei Variablen, twoBack und oneBack, die Tabelle. Das ist ein Durchlauf mit konstantem Aufwand pro Ziffer: O(n) Zeit, O(1) Speicher und überhaupt keine Rekursion.

Algorithmus

Setze twoBack = 0 und oneBack = 1, die Anzahl für das leere Präfix.
Beginne für jeden Index i mit current bei 0 und addiere oneBack, wenn Ziffer i nicht 0 ist.
Wenn i ≥ 1, Ziffer i-1 nicht 0 ist und die Ziffern i-1 und i eine Zahl von höchstens 26 bilden, addiere twoBack.
Verschiebe weiter: twoBack = oneBack, dann oneBack = current.
Gib nach der letzten Ziffer 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

Fast jede falsche Antwort auf dieses Problem geht auf die Nullen oder auf ein Memo zurück, das etwas vergisst.

0 als Buchstaben oder 06 als 6 zu behandeln. Eine Null kann nur 10 oder 20 abschließen, daher haben "30", "100" und "06" alle 0 Lesarten.
Ein zweistelliges Teilstück nur mit ≤ 26 zu prüfen. 05 ist als Zahl 5, aber kein Code. Prüfe, dass die erste der beiden Ziffern nicht 0 ist.
0 als Markierung für einen Memo-Slot zu verwenden, der noch nicht berechnet wurde. Viele Positionen haben tatsächlich 0 Lesarten, daher gelten diese Slots nie als gespeichert und werden bei jedem Aufruf erneut berechnet. Bei 44 Einsen gefolgt von Dreien und einer abschließenden 0 ist jeder Slot 0, und du kommst wieder auf etwa 10^11 Aufrufe.
Die Ziffer vor Index 0 auszulesen. Sichere die Prüfung auf zwei Ziffern mit i ≥ 1 ab: In Python liest s[-1] stillschweigend die letzte Ziffer aus, und andere Sprachen lesen außerhalb der Zeichenfolge.
s in eine einzelne Zahl umzuwandeln. Hundert Ziffern passen in keinen Ganzzahltyp, und bei der Umwandlung gehen führende Nullen verloren, die die Antwort verändern. Arbeite Ziffer für Ziffer.
In Lua und R beginnen Positionen bei 1, daher ist das Ende der Zeichenfolge Position n+1 und die erste Prüfung auf zwei Ziffern erfolgt an Position 2.

Häufige Fragen4

Wie hoch ist die Zeitkomplexität von Decode Ways?

Die Bottom-up-Lösung liest jede Ziffer einmal mit konstantem Aufwand und läuft daher in O(n)-Zeit und benötigt zusätzlichen Speicherplatz von O(1). Memoisierte Rekursion benötigt ebenfalls O(n)-Zeit, aber O(n)-Speicherplatz für das Memo und den Aufrufstapel. Einfache Rekursion ist exponentiell: Bei einer Zeichenfolge aus Einsen wächst die Anzahl der Aufrufe ungefähr wie 1.618^n.

Wie hängt Decode Ways mit Climbing Stairs zusammen?

Beide zählen die Möglichkeiten, eine Linie mit Schritten der Größe 1 und 2 zurückzulegen. Bei Climbing Stairs ist jeder Schritt erlaubt, daher entspricht die Anzahl einer Fibonacci-Zahl. Bei Decode Ways benötigt ein einstellig dargestellter Schritt eine Ziffer von 1 bis 9 und ein zweistelliger Schritt eine Zahl von 10 bis 26. Daher wird jeder Summand nur dann addiert, wenn seine Bedingung erfüllt ist. Eine Zeichenfolge aus Einsen erlaubt jeden Schritt, und ihre Anzahlen entsprechen genau den Fibonacci-Zahlen.

Wie gehst du in „Decode Ways“ mit Nullen um?

Eine 0 kann niemals allein ein Buchstabe sein, daher muss sie mit der Ziffer davor ein Paar bilden, und nur 10 und 20 sind Codes. In der Bottom-up-Schleife bedeutet das, dass eine 0 im Fall einer einzelnen Ziffer nichts hinzufügt und den Zählerstand von zwei Stellen zuvor nur nach einer 1 oder einer 2 hinzufügt. Eine führende 0, zwei Nullen hintereinander oder eine 0 nach einer Ziffer von 3 bis 9 ergibt als Antwort 0.

Kann Decode Ways mit O(1) Speicherplatz gelöst werden?

Ja. Die Anzahl für ein Präfix hängt nur von den Anzahlen für die beiden Präfixe ab, die ein bzw. zwei Ziffern kürzer sind. Daher ersetzen zwei Variablen die gesamte Tabelle. Bei jedem Schritt wird daraus die neue Anzahl berechnet und die Variablen werden um eine Position weitergeschoben.

Python

def numDecodings(s):
    # Schreibe hier den Code

Testfälle

Fall 1

Fall 2

Fall 3

Eingabe

s = "2611"

Erwartet

Decode Ways

Funktion

Einschränkungen

Beispiele

Tipps

Lösung

Probiere beide Lesarten mit Rekursion aus

Rekursion mit einem Memo

Bottom-up mit zwei Zählern

Stolperfallen und Grenzfälle

Häufige Fragen4

Ähnliche Aufgaben