我們先來描述這個問題:
您截獲了一條編碼為數字字串的秘密訊息。該訊息透過以下映射解碼:
「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 到 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]; }
Both the time and space complexity for this solution are 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中文網其他相關文章!