class Solution {
public:
    vector<int> memo;
    int getWays(string str,int currentIndex){
        // base case 
        if(currentIndex == str.length()){
            return 1;
        }
        if(currentIndex > str.length()){
            return 0;
        }
        if(memo[currentIndex] != 0){
            return memo[currentIndex];
        }
        int c1 = 0, c2 = 0;
        // take a single charracter 
        int sub = stoi(str.substr(currentIndex, 1));
        if(sub != 0){
            // recur for remaining
            c1 = getWays(str, currentIndex + 1);
        }
        // take 2 character at a time and check if lies betn 10 and 26
        sub = stoi(str.substr(currentIndex, 2));
        if(sub >= 10 && sub <= 26){
            // recur for remaining
            c2 = getWays(str, currentIndex + 2);
        } 
        return memo[currentIndex] = c1 + c2;
    }
    int numDecodings(string s) {
        int l = s.length();
        if(l == 0){
            return 0;
        }
        memo.assign(l+1, 0);
        return getWays(s, 0);
    }
};