首页 > 代码库 > leetcode第一刷_Decode Ways

leetcode第一刷_Decode Ways

这道题还挺难的。递归的思路是好想,不过不出意料的超时了。

dp嘛。想一下i-1的编码加上第i个编码会怎样,如果加上的这个编码不是0,那么这一位可以独立解码,那长为i的解码个数至少是长为i-1的解码个数。还有呢?如果i-1位是1,可以把i-1位和i位同时解码出来,还有呢?如果i-1位是2而i位是0-6中的数字,也可以同时解码这两位编码。满足这个条件的时候,当前长度的解码个数还要加上i-2时的解码个数。

完全可以用一个数组存放过去的结果,但是很明显,当前的结论只与前一个和前前一个结果有关系。只要用三个数分别表示当前的,之前一个的,之前两个的解码个数,就可以了。具体的实现细节如下:

class Solution {
public:
    int numDecodings(string s) {
        if(s==""||s[0]==‘0‘)
            return 0;
        if(s.length() == 1)
            return 1;
        int res = 0, res1 = 1, res2 = 1;
        for(int i=2;i<=s.length();i++){
        	res = 0;
            if(s[i-1] != ‘0‘)
                res += res1;
            if(s[i-2] == ‘1‘||(s[i-2]==‘2‘ && s[i-1]<‘7‘))
                res += res2;
            res2 = res1;
            res1 = res;
        }
        return res;
    }
};