91. 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 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).

class Solution {
public:
    int numDecodings(string s) {
        int n=s.size();
        vector<int> dp(n+1);
        dp[0]=1;
        dp[1]=0==s[0]?0:1;
        for(int i=2;i<=s.size();++i)
        {
            int first=s[i-1]-0;
            int second=(s[i-2]-0)*10+first;
            if(first>=1&&first<=9)dp[i]=dp[i-1];
            if(second>=10&&second<=26) dp[i]+=dp[i-2];
        }
        return dp[n];
    }
};
相关文章
相关标签/搜索
每日一句
    每一个你不满意的现在,都有一个你没有努力的曾经。
公众号推荐
   一个历史类的公众号,欢迎关注
一两拨千金