Decode Ways

MediumDynamic Programming

Count the ways to decode a digit string into letters, where 'A'..'Z' map to '1'..'26'.

Constraints

1 <= s.length <= 100
s contains only digits

Rolling DP over prefixes

Time O(n)Space O(1)

Ways to decode the first i characters depend on whether the last digit forms a valid single letter (1-9) and whether the last two digits form a valid pair (10-26). Track the last two counts.

#include <bits/stdc++.h>
using namespace std;

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 cur = 0;
        if (s[i] != '0') cur += prev1;
        int two = (s[i - 1] - '0') * 10 + (s[i] - '0');
        if (two >= 10 && two <= 26) cur += prev2;
        prev2 = prev1;
        prev1 = cur;
    }
    return prev1;
}