Decode Ways @LeetCode

A message containing letters from A-Z is being encoded to numbers using the following mapping:

'A' -> 1
'B' -> 2
...
'Z' -> 26

Given an encoded message containing digits, determine the total number of ways to decode it.

For example,
Given encoded message "12", it could be decoded as "AB" (1 2) or "L" (12).

The number of ways decoding "12" is 2.

	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()];
	}
	}

view raw NumDecodings.java hosted with ❤ by GitHub