Decode Ways 512

Question

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.

Example

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

The number of ways decoding 12 is 2.

Solution

num[i]代表前i个元素有多少种decode方法。

初始化：num[0]=1, num[1]=s.charAt(i-1)=='0'? 0 : 1

状态函数：

分两种情况讨论

case 1: 第i位元素单独decode（如果为'0'则不能单独decode）
num[i]=num[i-1]

case 2: 第i位元素和前一位元素一起decode（第i位元素和第i－1位元素组成的两位数必须在10~26范围内）
num[i]+=num[i-2]

代码如下：

public class Solution {
    /**
     * @param s a string,  encoded message
     * @return an integer, the number of ways decoding
     */
    public int numDecodings(String s) {
        // Write your code here
        if(s == null || s.length() == 0){
            return 0;
        }

        int n = s.length();
        int[] num = new int[n + 1];
        num[0] = 1;
        num[1] = s.charAt(0) != '0' ? 1 : 0;

        for(int i = 2; i <= n; i++){
            if(s.charAt(i - 1) != '0'){
                num[i] = num[i - 1];
            }

            int val = (s.charAt(i - 2) - '0') * 10 + s.charAt(i - 1) - '0';
            if(val >= 10 && val <= 26){
                num[i] += num[i - 2];
            }
        }

        return num[n];
    }
}