lintcode512. 解码方法

末蓝、 2023-07-18 05:54 74阅读 0赞

有一个消息包含A-Z通过以下规则编码

‘A’ -> 1
‘B’ -> 2
…
‘Z’ -> 26
现在给你一个加密过后的消息，问有几种解码的方式

样例
样例 1:
输入: "12"
输出: 2
解释: 它可以被解码为 AB (1 2) 或 L (12).
样例 2:
输入: "10"
输出: 1
注意事项
we can't decode an empty string. So you should return 0 if the message is empty.
class Solution {
public:
    /**
     * @param s: a string,  encoded message
     * @return: an integer, the number of ways decoding
     */
    int numDecodings(string &s) {
        // write your code here
        if (s.size() <= 0) {
            return 0;
        }
        vector<int> dp(s.size()+1);
        dp[0]=1;
        for (int i = 1; i <= s.size(); i++) {
            if(s[i-1]=='0') dp[i]=0;
            else
            {
                dp[i]+=dp[i-1];
            }
            if(i>1)
            {
                int num=atoi(s.substr(i - 2, 2).c_str());
                if(num>=10&&num<=26) dp[i]+=dp[i-2];
            }
        }
        return dp[s.size()];
    }
};