91. Decode Ways

class Solution {
    public int numDecodings(String s) {
        // 定义 dp[i] 为前 i 个字符组成的字符串对应的解码方法数
        int[] dp = new int[s.length() + 1];
        dp[0] = 1; // 0 个字符时解码方法数为 1

        for (int j = 1; j <= s.length(); j++) {
            char c = s.charAt(j - 1);

            // 作为一个字符解码时
            if (c >= '1' && c <= '9') {
                dp[j] = dp[j - 1];
            }

            // 作为两个字符解码时
            if (j - 2 >= 0) {
                char prevChar = s.charAt(j - 2);
                if (prevChar == '1' || (prevChar == '2' && c <= '6')) {
                    dp[j] += dp[j - 2];
                }
            }
        }

        return dp[s.length()];
    }
}

Reference

91. Decode Ways