/**
 * @author li_zhe
 * 思路leetcode，DP
 * 如果能和前一位组合成一个1-26的数,dp[i] = dp[i-1] + dp[i-2]
 */
public class DecodeWays {

	public int numDecodings(String s) {
		if(s == null || s.length() == 0) return 0;
		int[] ways = new int[s.length() + 1];
		ways[0] = 1;
		ways[1] = s.charAt(0) == '0' ? 0 : 1;
		for(int i = 2; i <= s.length(); i++){
			int lastOne = Integer.parseInt(s.substring(i - 1, i));
			int lastTwo = Integer.parseInt(s.substring(i - 2, i));
			if(lastOne >= 1 && lastOne <= 9) ways[i] = ways[i - 1];
			if(lastTwo >= 10 && lastTwo <= 26) ways[i] += ways[i - 2];
		}
		return ways[s.length()];
	}
	
	public static void main(String[] args) {
		DecodeWays decode = new DecodeWays();
		System.out.println(decode.numDecodings("226"));
		System.out.println(decode.numDecodings("12"));
		System.out.println(decode.numDecodings("122331112212321"));
	}

}