Decode Ways @leetcode

NumDecodings.java

package leetcode.dp;

/**
 * Solution: Linear DP
 * nums[i] 代表前0个digit可以有多少中solution. 
 * 1. 对于每一个非0位, num[i] = num[i-1]. 这里只计算了single digit的问题 
 * 2. 对于two digit, 看下范围是否是10-26, 如果是 num[i] += num[i-2] solution的种类等于num[i-2]的，也就是前面集中，这类就是几种
 * 3. test case, 最后一位如果是0，在range，那就是num[i-2]种可能，如果不在，这个String不是合法的.
 * 
 * Reference: http://leetcodenotes.wordpress.com/2013/07/17/decode-ways/
 * 
 * @author jeffwan
 * @date Apr 17, 2014
 */
public class NumDecodings {
	public int numDecodings(String s) {
		if (s == null || s.length() == 0) {
			return 0;
		}
		
		int[] nums = new int[s.length() + 1];
		nums[0] = 1;
		nums[1] = s.charAt(0) != '0' ? 1 : 0;
		
		for (int i = 2; i <= s.length(); i++) {
			if (s.charAt(i - 1) != '0') {
				nums[i] = nums[i - 1];
			}
			
			int twoDigits = (s.charAt(i - 2) - '0') * 10 + s.charAt(i - 1) - '0'; 
			if (twoDigits >= 10 && twoDigits <= 26) {
				nums[i] += nums[i - 2];
			}
		}
		
		return nums[s.length()];
    }
}