/**
1. 状态定义: f[i] 表示由前i个数存在多少种解码方法
2. 状态计算: 以最后一个数i划分
    2.1 s[i] 自己成为一个解码
    2.2 s[i] 与 s[i-1] 共同解码

3.边界:  f[~] = 0 , f[0] = 1 ,  f[1] = (s[0] == '0' ? 0 : 1)
*/

class Solution {
    public int numDecodings(String s) {
        if (s == null || s.length() == 0 || (s.length() == 1 && s.charAt(0) == '0')) return 0;
        int n = s.length();
        int[] f = new int[n+1];
        f[0] = 1;
        f[1] = s.charAt(0) == '0' ? 0 : 1;
        for (int i = 2 ; i<= n; i++){
            int single = s.charAt(i-1) - '0';
            if (0 < single && single <= 9) f[i] += f[i-1];
            int pair = 10 * (s.charAt(i-2) - '0') + single;
            if (10 <= pair && pair <= 26) f[i] += f[i-2];
        }
        return f[n];
    }
}