Ways to Decode

• Time : $O(|A|)$
• Space : $O(|A|)$

long long dp[101010], mod = 1e9 + 7;
long long helper(string& A, int p) {
    if(A.size() == p) return 1;
    if(dp[p] != -1) return dp[p];
    if(A[p] == '0') return 0;
    if(A[p] >= '3') return dp[p] = helper(A, p + 1);
    if(p + 1 == A.size()) return dp[p] = helper(A, p + 1);
    if(A[p] == '1') return dp[p] = (helper(A,p+1) + helper(A,p+2)) % mod;
    if(A[p + 1] >= '7') return dp[p] = helper(A, p + 1);
    return dp[p] = (helper(A,p+1) + helper(A,p+2)) % mod;
}
int Solution::numDecodings(string A) {
    memset(dp,-1,sizeof dp);
    return helper(A,0);
}