LeetCode-Meditationen: Wege entschlüsseln

Beginnen wir mit der Beschreibung dieses Problems:

Sie haben eine geheime Nachricht abgefangen, die als Zahlenfolge kodiert ist. Die Nachricht wird über folgende Zuordnung 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.

Geben Sie bei einer gegebenen Zeichenfolge s, die nur Ziffern enthält, die Anzahl der Möglichkeiten zum Dekodieren zurück. 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.length <= 100
• 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 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;




<p>Ä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.</p>

<p>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.<br>
Beachten Sie, dass sich <em>nicht in der Lage zu dekodieren</em> von <em>überhaupt keine Dekodierung durchzuführen</em> unterscheidet: Im ersten Fall beträgt die Anzahl der Dekodierungsmöglichkeiten 0, im zweiten Fall (wie Wir haben es gerade mit dp[0] gemacht), man kann sagen, dass die Anzahl der Möglichkeiten zum Dekodieren 1 beträgt.</p>

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

<pre class="brush:php;toolbar:false">dp[1] = (s[0] === '0') ? 0 : 1;

Jetzt können wir mit der Iteration ab dem dritten Index beginnen. Wir schauen uns gleichzeitig die vorherige Ziffer und die beiden vorherigen Ziffern an.

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 <= s.length; i++) {
  const prevDigit = s[i - 1];
  const twoPrevDigits = s.slice(i - 2, i);
  if (+prevDigit !== 0) {
    dp[i] += dp[i - 1];
  }

  if (10 <= +twoPrevDigits && +twoPrevDigits <= 26) {
    dp[i] += dp[i - 2];
  }
}

At this point, we have the result in the last index (which corresponds to s.length) so we can just return it:

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

  return dp[s.length]; 
}

Overall, this is how our solution looks like:

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 <= s.length; i++) {
    const prevDigit = s[i - 1];
    const twoPrevDigits = s.slice(i - 2, i);
    if (+prevDigit !== 0) {
      dp[i] += dp[i - 1];
    }

    if (10 <= +twoPrevDigits && +twoPrevDigits <= 26) {
      dp[i] += dp[i - 2];
    }
  }

  return dp[s.length];
}

Time and space complexity

Both the time and space complexity for this solution are $O(n)$O(n) as we iterate through all the characters doing a constant operation, and we have to keep an array whose size will grow as our input size increases.

Next up is the problem called Coin Change. Until then, happy coding.

Das obige ist der detaillierte Inhalt vonLeetCode-Meditationen: Wege entschlüsseln. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!