Decode Ways

A message containing letters fromA-Zis 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.

分析

The state transition equation is an ideal situation, but we still find the rule, the relationship between s[I and s[I - 1]] which is divided into the following categories:

1)s[ i ] Can exist independently, which can be decoded separately, and the number of combinations to form a combination of character s[I] with the front post can be decoded, which is legal code.

2)s[ i ] Can exist independently, which can be decoded separately, but combined with the front of the formation of characters cannot be the number of combinations, namely the number of code combinations illegal, could not be parsed.

3)s[ i ] Cannot exist independently, the only one, is the s[I] as the '0', but can be attached in front of the character, the formation of combinatorial number, form a legal code.

4)s[ i ] Cannot exist independently, but also can not tell the preceding character to form a combination of numbers, then, is the wrong code, could not be parsed.

So we see, in these cases our equation of state is what kind of.

1)This of course is the perfect rules we found in the chart, f [ i ] = f [ i - 1] + f [ i - 2]

2)This situation is that we summarized in chart first, so f[ i ] = f [ i - 1]

3)This situation is that we summarized in chart second, then f [ i ] = f [ i - 2]

Be careful:

1 here when we set condition, because the relationship to the f[I 2], so we will open more space for good.

2 judge s[0], if the '0' is returned.

图例

代码

class Solution {
    public int numDecodings(String s) {
        //base case 
        if(s.isEmpty() || s.charAt(0)=='0') return 0;
        if(s.length()==1) return 1;

        int curWay = 1;
        int preWay = 1;

        for(int i = 1; i<s.length(); i++){
            int w = 0;
            if(!isValid(s.charAt(i)) && !isValid(s.charAt(i-1),s.charAt(i)))  return 0;
            if(isValid(s.charAt(i)))   w = curWay;
            if(isValid(s.charAt(i-1),s.charAt(i)))   w = w + preWay ;
            preWay  = curWay;
            curWay = w;
        }
        return curWay;    
    }
    // 1-digit eg: 1204 
    private boolean isValid(char c) {
        return c!='0';
    }
    // 2-digits eg: 36
    private boolean isValid(char c1, char c2) {
        int num = (c1-'0') *10 + (c2-'0');
        return num>=10 && num<=26;
    }
}