Decode Ways

Number of decodings of a digit string under the A=1, B=2, ..., Z=26 mapping — 1D DP.

Medium
Time O(n) Space O(1)
LeetCode
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#

Decode Ways
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;
}
};

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#

Search ESC

Keyboard shortcuts

Shortcuts are disabled while typing in inputs.