public int numDecodings(String s) {
        int len = s.length();
        if(len == 0) return 0;
        int[] memo = new int[len];
        if(isValid(s, 0, 1)) memo[0] = 1;
        if(len == 1) return memo[0];
        if(isValid(s, 1, 2)) memo[1] += memo[0];
        if(isValid(s, 0, 2)) memo[1]++;

        for(int i = 2; i < len; i++){
            if(isValid(s, i, i + 1)) memo[i] += memo[i - 1];
            if(isValid(s, i - 1, i + 1)) memo[i] += memo[i - 2];
        }
        return memo[len - 1];
    }