public int numDecodings(String s) {

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

return 0;

}

int n = s.length();

char[] ss = s.toCharArray();

int[] dp = new int[n + 1];

dp[0] = 1; // 1 to help build dp

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

for (int i = 2; i <= n; i++) {

int oneDigit = ss[i - 1] - '0';

if (oneDigit >= 1 && oneDigit <= 9) {

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

}

int twoDigit = (ss[i - 1] - '0') + 10 * (ss[i - 2] - '0');

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

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

}

}

return dp[n];

}

public int numDecodings(String s) {

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

return 0;

}

if (s.length() == 1) {

return 1;

}

int n = s.length();

int[] dp = new int[n + 1];

dp[0] = 1;

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

for (int i = 2; i <= n; i++) {

if (s.charAt(i - 1) != '0') {

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

}

int twoDigit = (s.charAt(i - 2) - '0') * 10 + (s.charAt(i - 1) - '0');

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

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

}

}

return dp[n];

}