function numDecodings(s) {
  if (!s.length || s.charAt(0) === '0') {
    return 0
  }
  var dp = new Array(s.length + 1).fill(0)
  dp[0] = 1;
  for (var i = 1; i < dp.length; i++) {
    dp[i] = (s.charAt(i - 1) == '0') ? 0 : dp[i - 1];
    if (i > 1 && (s.charAt(i - 2) == '1' || (s.charAt(i - 2) == '2' && s.charAt(i - 1) <= '6'))) {
      dp[i] += dp[i - 2];
    }
  }
  return dp[s.length];
}