Decode Ways — Counting DP

Problem

A string of digits can be decoded as letters (1→A, ..., 26→Z). Count total decodings.

Example: "226" → 3 (2-2-6, 22-6, 2-26)

Approach — DP with 1 and 2-digit checks

dp[i] = ways to decode first i chars.

If s[i-1] != '0': dp[i] += dp[i-1]
If 10 <= int(s[i-2:i]) <= 26: dp[i] += dp[i-2]

Time: O(n) | Space: O(1)

Solutions

Python

class Solution:
    def numDecodings(self, s: str) -> int:
        if 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:i+1])
            if 10<=two<=26: curr+=prev2
            prev2,prev1=prev1,curr
        return prev1

C++

class Solution {
public:
    int numDecodings(string s){
        if(s[0]=='0') return 0;
        int prev2=1,prev1=1;
        for(int i=1;i<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;
    }
};

Java

class Solution {
    public int numDecodings(String s){
        if(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=Integer.parseInt(s.substring(i-1,i+1));
            if(two>=10&&two<=26) curr+=prev2;
            prev2=prev1; prev1=curr;
        }
        return prev1;
    }
}

Complexity

Time: O(n) | Space: O(1)