package leetcode._91_;

class Solution2 {

public int numDecodings(String s) { // 动态规划

if (s == null || s.length() == 0) {

return 0;

}

int[] dp = new int[s.length() + 1];

dp[0] = 1;

dp[1] = s.charAt(0) != '0' ? 1 : 0;

for (int i = 2; i <= s.length(); i++) {

int first = Integer.parseInt(s.substring(i - 1, i));

int second = Integer.parseInt(s.substring(i - 2, i));

if (first > 0 && first < 10) {

dp[i] += dp[i - 1];

}

if (second >= 10 && second <= 26) {

dp[i] += dp[i - 2];

}

}

return dp[s.length()];

}

}