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位元整數。

例如：

雷雷

或：

雷雷

或：

雷雷

限制是：

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

---

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

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

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

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

雷雷

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

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

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

雷雷

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

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

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

雷雷

注意

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

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中文網其他相關文章！