LeetCode 冥想：解碼方法

發佈於2024-08-01

LeetCode Meditations: Decode Ways

我們先來描述這個問題：

您截獲了一條編碼為數字字串的秘密訊息。該訊息透過以下映射進行解碼：

“1”->“A”“2”->“B”...“25”->“Y”“26”->“Z”

但是，在解碼訊息時，您意識到可以透過多種不同的方式解碼訊息，因為某些程式碼包含在其他程式碼中（「2」和「5」與「25」）。

例如「11106」可以解碼為：

“AAJF”，分組為 (1, 1, 10, 6)

「KJF」與分組 (11, 10, 6)

分組 (1, 11, 06) 無效，因為「06」不是有效代碼（只有「6」有效）。

注意：可能存在無法解碼的字串。

給定一個僅包含數字的字串 s，傳回對其進行解碼的方式數。如果整個字串無法以任何有效方式解碼，則傳回 0.

產生測試案例，以便答案適合32位元整數。

例如：

Input: s = "12"

Output: 2

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

或：

Input: s = "226"

Output: 3

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

或：

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.

約束條件是：

1
s 僅包含數字，並且可能包含前導零。

我認為這是您乍看之下不那麼困難的問題之一，直到您嘗試解決它為止。

首先，讓我們從最簡單的見解開始：一個字元可以被解碼為它本身（僅一個字元）或兩位數的一部分。
如果它是第一個選項，我們只能有從 1 到 9 的數字，因為 0 本身不映射到任何東西。
但是，兩位數的範圍可以是 10 到 26。

與本章前面的問題一樣，我們可以先建立一個 dp 陣列來保存迭代字串時每個字元的解碼方式數量。
與爬樓梯非常相似，我們必須使用長度 s.length 1 初始化數組，因為我們需要考慮我們尚未解碼任何內容的事實。
換句話說，當沒有字元時，只有一種方式來「解碼」：根本不解碼。

因此，我們可以將所有值初始化為 0，除了第一個索引將是 1。

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

dp[0] = 1;

同樣，與前面的問題類似，我們必須保留底部的兩個值，因此我們必須初始化數組的第二個槽，它對應於解碼字串中第一個字元的方法數。

我們知道，如果它是“0”，我們就無法對其進行解碼，因此在這種情況下解碼它的方法數將為 0。
請注意，無法解碼與根本不進行任何解碼不同：在第一種情況下，解碼方式的數量為0，但在第二種情況下（如我們剛剛用dp[0]做的），可以說解碼的方式數是1。

在所有其他情況下，只有一種方法對其進行解碼，因為它只是一個字元。因此，我們將相應地初始化 dp[1]：

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

現在我們可以從第三個索引開始迭代。我們將同時查看前一個數字和前兩個數字。

只要前一個數字不是數字 0，我們就可以新增數組前一個槽的任何內容。

並且，只要前兩位數字構成10到26之間的數字，我們也可以加入對應的解。總而言之，它可以看起來像這樣：

for (let i = 2; i 



筆記
我們使用方便的一元加運算子將字串字元轉換為數字。從問題約束我們知道字串 s 只包含數字。 


此時，我們在最後一個索引（對應於 s.length）中得到了結果，因此我們可以返回它：


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

  return dp[s.length]; 
}




總的來說，我們的解決方案是這樣的：


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 




  
  
  時間和空間複雜度


此解決方案的時間和空間複雜度均為 $O (n) O(n)$ 




接下來是硬幣找零的問題。在那之前，祝您編碼愉快。