(每日算法)LeetCode --- Decode Ways

(每日算法)LeetCode --- Decode Ways

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.

/*每次對於當前的字符判斷是否屬於1-9（0肯定不行，因為0不在1-26中），如果屬於，那麼當前的字符可以被decode，並且和f[n-1]組合，f[n] += f[n-1]
然後對於當前字符和前一個字符組成的字符串判斷是否屬於10-26，如果屬於，那麼這兩個字符可以被decode，並且和f[n-2]組合，f[n] += f[n-2]
*/
class Solution {
public:
    int numDecodings(string s) {
        int * a;
        a = new int[s.size()+1];
        memset(a,0,(s.size()+1)*sizeof(int));
        if(s.size() == 0)
            return 0;
        a[0] = 1;
        for(int i = 1; i <= s.size(); i++)
        {
            if(s[i-1] != '0')
                a[i] += a[i-1];
            if(i -2 >= 0 && s[i-1] - '0' + 10 * (s[i-2] - '0') <= 26 && s[i-1] - '0' + 10 * (s[i-2] - '0') >= 10)
                a[i] += a[i-2];
        }
        return a[s.size()];
    }
};