class Solution {
    Map<String, Integer> cache = new HashMap<>();
    
    int total = 0;
    public int numDecodings(String s) {
        return numDecodingsAux(s);
    }
    
    public int numDecodingsAux(String s) {
        if(s.length() == 0) {
            return 1;
        }
        
        if(cache.containsKey(s))
            return cache.get(s);
        
        int a1 = 0;
        int a2 = 0;
        if(s.length() > 0) {
            if(isValid(s.substring(0, 1))) {
                a1 = numDecodingsAux(s.substring(1, s.length()));
            }
        }
        
        if(s.length() > 1) {
            if(isValid(s.substring(0, 2))) {
                a2 = numDecodingsAux(s.substring(2, s.length()));
            }
        }
        
        cache.put(s, a1 + a2);
        return cache.get(s);
    }
    
    public boolean isValid(String s) {
        if(s.charAt(0) == '0') {
            return false;
        }
        if(s.length() == 2) {
            int v = Integer.parseInt(s);
            if(v > 26) {
                return false;
            }
        }
        return true;
    }
}