Beginnen wir mit der Beschreibung dieses Problems:

Sie haben eine geheime Nachricht abgefangen, die als Zahlenfolge kodiert ist. Die Nachricht wird über das folgende Mapping dekodiert:

"1" -> 'A' "2" -> 'B' ... "25" -> 'Y' "26" -> 'Z'

Beim Dekodieren der Nachricht stellen Sie jedoch fest, dass es viele verschiedene Möglichkeiten gibt, die Nachricht zu dekodieren, da einige Codes in anderen Codes enthalten sind („2“ und „5“ vs. „25“).

Zum Beispiel kann „11106“ dekodiert werden in:

• „AAJF“ mit der Gruppierung (1, 1, 10, 6)
• „KJF“ mit der Gruppierung (11, 10, 6)
• Die Gruppierung (1, 11, 06) ist ungültig, da „06“ kein gültiger Code ist (nur „6“ ist gültig).

Hinweis: Möglicherweise gibt es Zeichenfolgen, die nicht dekodiert werden können.

Gegebene Zeichenfolgen, die nur Ziffern enthalten, geben die Anzahl der Möglichkeiten zurück, um sie zu dekodieren. Wenn die gesamte Zeichenfolge nicht auf gültige Weise dekodiert werden kann, geben Sie 0 zurück.

Die Testfälle werden so generiert, dass die Antwort in eine 32-Bit-Ganzzahl passt.

Zum Beispiel:

Input: s = "12"

Output: 2

Explanation: "12" could be decoded as "AB" (1 2) or "L" (12).

Oder:

Input: s = "226"

Output: 3

Explanation: "226" could be decoded as "BZ" (2 26), "VF" (22 6), or "BBF" (2 2 6).

Oder:

Input: s = "06"

Output: 0

Explanation: "06" cannot be mapped to "F" because of the leading zero ("6" is different from "06"). In this case, the string is not a valid encoding, so return 0.

Die Einschränkungen sind:

• 1
• s enthält nur Ziffern und kann führende Nullen enthalten.

Ich denke, das ist eines dieser Probleme, von denen man auf den ersten Blick denkt, dass sie nicht so schwierig sind, bis man versucht, es zu lösen.

Beginnen wir zunächst mit der einfachsten Erkenntnis: Ein Zeichen kann entweder als es selbst (als nur ein Zeichen) oder als Teil einer zweistelligen Zahl dekodiert werden.
Wenn es die erste Option ist, können wir nur Ziffern von 1 bis 9 haben, da 0 allein nichts zugeordnet wird.
Eine zweistellige Zahl kann jedoch zwischen 10 und 26 liegen.

Wie bei den vorherigen Problemen in diesem Kapitel können wir damit beginnen, ein dp-Array zu erstellen, um die Anzahl der Dekodierungsmöglichkeiten für jedes Zeichen zu speichern, während wir die Zeichenfolge durchlaufen.
Ganz ähnlich wie bei Climbing Stairs müssen wir unser Array mit der Länge s.length 1 initialisieren, da wir die Tatsache berücksichtigen müssen, dass wir noch nichts dekodiert haben.
Mit anderen Worten: Wenn keine Zeichen vorhanden sind, gibt es nur eine eine Möglichkeit zum „Dekodieren“: überhaupt keine Dekodierung.

Wir können also alle Werte als Nullen initialisieren, mit Ausnahme des ersten Index, der 1 sein wird.

let dp = Array.from({ length: s.length   1 }, () => 0);

dp[0] = 1;

Ähnlich wie bei den vorherigen Problemen müssen wir auch hier die unteren beiden Werte beibehalten, also müssen wir den zweiten Slot unseres Arrays initialisieren, der der Anzahl der Möglichkeiten entspricht, das erste Zeichen in der Zeichenfolge zu dekodieren.

Wir wissen, dass wir es nicht dekodieren können, wenn es „0“ ist, daher ist die Anzahl der Möglichkeiten, es zu dekodieren, in diesem Fall 0.
Beachten Sie, dass sich nicht in der Lage ist zu dekodieren von überhaupt keine Dekodierung durchführt unterscheidet: Im ersten Fall beträgt die Anzahl der Dekodierungsmöglichkeiten 0, im zweiten Fall jedoch (wie Wir haben es gerade mit dp[0] gemacht. Man kann sagen, dass die Anzahl der Dekodierungsmethoden 1 beträgt.

In allen anderen Fällen gibt es nur eine Möglichkeit, es zu dekodieren, da es sich nur um ein einzelnes Zeichen handelt. Also initialisieren wir dp[1] entsprechend:

dp[1] = (s[0] === '0') ? 0 : 1;

Jetzt können wir mit der Iteration ab dem dritten Index beginnen. Wir werden uns sowohl die vorherige Ziffer als auch die beiden vorherigen Ziffern gleichzeitig ansehen.

Solange die vorherige Ziffer nicht die Zahl 0 ist, können wir alles hinzufügen, was sich im vorherigen Slot unseres Arrays befindet.

Und solange die beiden vorherigen Ziffern eine Zahl zwischen 10 und 26 darstellen, können wir auch die entsprechende Lösung hinzufügen. Alles in allem kann es so aussehen:

for (let i = 2; i 



Notiz
Wir wandeln die Zeichenketten mit dem praktischen unären Plus-Operator in Zahlen um. Aus den Problemeinschränkungen wissen wir, dass die Zeichenfolge s nur Ziffern enthält.


An diesem Punkt haben wir das Ergebnis im letzten Index (der s.length entspricht), sodass wir es einfach zurückgeben können:


function numDecodings(s: string): number {
  /* ... */

  return dp[s.length]; 
}




Insgesamt sieht unsere Lösung so aus:


function numDecodings(s: string): number {
  let dp = Array.from({ length: s.length   1 }, () => 0);

  dp[0] = 1;
  dp[1] = (s[0] === '0') ? 0 : 1;

  for (let i = 2; i 




  
  
  Zeit- und Raumkomplexität


Sowohl der zeitliche als auch der räumliche Aufwand für diese Lösung sind $O(n)$An)

 Da wir alle Zeichen durchlaufen und eine konstante Operation ausführen, müssen wir ein Array behalten, dessen Größe mit zunehmender Eingabegröße zunimmt.


Als nächstes kommt das Problem namens Münzwechsel. Bis dahin viel Spaß beim Codieren.