Decode Ways

Java

public class Solution {
    /**
     * @param s: a string,  encoded message
     * @return: an integer, the number of ways decoding
     */
		public int numDecodings(String s) {
			if (s == null || s.length() == 0) return 0;
			
			int n = s.length();
			int[] dp = new int[n + 1];
			dp[0] = 1;
			dp[1] = s.charAt(0) == '0' ? 0 : 1; //0为非法字符
			for (int i = 1; i < n; i++) { //i是index in s
				//求 dp[i+1] → 前i个数字能组成的答案
				if (s.charAt(i) != '0') {
					dp[i + 1] += dp[i];
				} 
				int twoDigit = (s.charAt(i - 1) - '0') * 10 + (s.charAt(i) - '0');
				if (twoDigit >= 10 && twoDigit <= 26) {
					dp[i + 1] += dp[i - 1];
				}
			}
			return dp[n];
		}
}