LeetCode 冥想：解碼方法

我們先來描述這個問題：

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

「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.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.

以上是LeetCode 冥想：解碼方法的詳細內容。更多資訊請關注PHP中文網其他相關文章！