91. Decode Ways

problem desctiption

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

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

Given a non-empty string containing only digits, determine the total number of ways to decode it.

Example 1:

Input: "12"
Output: 2
Explanation: It could be decoded as "AB" (1 2) or "L" (12).

Example 2:

Input: "226"
Output: 3
Explanation: It could be decoded as "BZ" (2 26), "VF" (22 6), or "BBF" (2 2 6).

algorithm thought

典型的动态规划问题，当前数字如果可以和前面数字组合成为一个合法的字符，当前decode way就可以加上前两次的decode way，如果当前的数字不等于0，就能加上前一个次的decode way。

code

class Solution {
public:
    int numDecodings(string s) {
        if(s[0]=='0')
            return 0;
        vector<int>res(s.size()+1);
        res[0]=1;res[1]=1;
        for(int i=1;i<s.size();++i){
            if((s[i-1]=='1')||(s[i-1]=='2'&&s[i]<='6'))
                res[i+1]+=res[i-1];
            if(s[i]!='0')
                res[i+1]+=res[i];
        }
        return res.back();
    }
};

algorithm analysis

一次遍历处理数组，时间复杂度O(n),使用一维数组保存结果，空间复杂度O(n)