Decode Ways
Number of decodings of a digit string under the A=1, B=2, ..., Z=26 mapping — 1D DP.
3 min read
dp string
Problem#
Each digit (1–26) maps to a letter A–Z. Return the number of ways to decode s. Leading 0 is invalid as a single decode.
Examples#
"12"→2("AB","L")"226"→3"06"→0
Constraints#
1 <= s.length <= 100.
Approach#
dp[i] = decodings of s[:i]. dp[i] += dp[i-1] if s[i-1] != '0'; dp[i] += dp[i-2] if the two-digit s[i-2..i-1] ∈ [10, 26]. Roll to two scalars.
Solution#
class Solution {public: int numDecodings(string s) { if (s.empty() || s[0] == '0') return 0; int prev2 = 1, prev1 = 1; for (int i = 1; i < (int)s.size(); ++i) { int curr = 0; if (s[i] != '0') curr += prev1; int two = (s[i - 1] - '0') * 10 + (s[i] - '0'); if (two >= 10 && two <= 26) curr += prev2; prev2 = prev1; prev1 = curr; } return prev1; }};func numDecodings(s string) int { if len(s) == 0 || s[0] == '0' { return 0 } prev2, prev1 := 1, 1 for i := 1; i < len(s); i++ { curr := 0 if s[i] != '0' { curr += prev1 } two := int(s[i-1]-'0')*10 + int(s[i]-'0') if two >= 10 && two <= 26 { curr += prev2 } prev2 = prev1 prev1 = curr } return prev1}class Solution: def numDecodings(self, s: str) -> int: if not s or s[0] == '0': return 0 prev2, prev1 = 1, 1 for i in range(1, len(s)): curr = 0 if s[i] != '0': curr += prev1 two = int(s[i - 1]) * 10 + int(s[i]) if 10 <= two <= 26: curr += prev2 prev2, prev1 = prev1, curr return prev1function numDecodings(s) { if (!s || s[0] === '0') return 0; let prev2 = 1, prev1 = 1; for (let i = 1; i < s.length; i++) { let curr = 0; if (s[i] !== '0') curr += prev1; const two = (s.charCodeAt(i - 1) - 48) * 10 + (s.charCodeAt(i) - 48); if (two >= 10 && two <= 26) curr += prev2; prev2 = prev1; prev1 = curr; } return prev1;}class Solution { public int numDecodings(String s) { if (s.isEmpty() || s.charAt(0) == '0') return 0; int prev2 = 1, prev1 = 1; for (int i = 1; i < s.length(); i++) { int curr = 0; if (s.charAt(i) != '0') curr += prev1; int two = (s.charAt(i - 1) - '0') * 10 + (s.charAt(i) - '0'); if (two >= 10 && two <= 26) curr += prev2; prev2 = prev1; prev1 = curr; } return prev1; }}function numDecodings(s: string): number { if (!s || s[0] === '0') return 0; let prev2 = 1, prev1 = 1; for (let i = 1; i < s.length; i++) { let curr = 0; if (s[i] !== '0') curr += prev1; const two = (s.charCodeAt(i - 1) - 48) * 10 + (s.charCodeAt(i) - 48); if (two >= 10 && two <= 26) curr += prev2; prev2 = prev1; prev1 = curr; } return prev1;}Editorial#
Two transitions per character: standalone (must be 1–9) or paired with the previous (must be 10–26). The leading-zero check seeds the recurrence; mid-string 0s without a valid preceding 1 or 2 zero out the answer.
Complexity#
- Time: O(n).
- Space: O(1).
Concept revision#
Related#