首页 » 编程之美 » 正文

[leetcode_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 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.

开始用搜索,超时。

后来一想如果从后面前找,这样的话很多多余的状态不仅存下来了,而且不会重复计算。

然后注意0存在的情况。

class Solution {
public:
    int counts[10000];
    int numDecodings(string s) {
        if(s.length() <= 0 || (s.length() == '1' && s[0] == '0'))return 0;
        if(s[s.length()-1] != '0')counts[s.length() - 1] = 1;
        else counts[s.length()-1] = 0;
        counts[s.length()] = 1;
        for(int i = s.length()-2;i >= 0;i--) {
            if(s[i] == '0') {
                counts[i] = 0;
                continue;
            }
            if(s[i] == '1' || (s[i] == '2'&&s[i+1] <= '6'))counts[i] = counts[i+1] + counts[i+2];
            else
                counts[i] = counts[i+1];
        }
        return counts[0];
    }
};

发表评论