例题解析 -- 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.

*******************************************************************************

分析：

    前i-1共cur种，前i-2共prev种，当把第i个字符加入考虑时，会出现三种情况：

        -- 第i个字符为0，那么第i个加进去以后就是prev种（后面是固定的，所以不会增长）

        -- 第i-1和第i个字符可以合并为一个整体，那么第i个加进去以后就是prev + cur种

        -- 第i-1和第i个字符不能合并为一个整体，那么第i个加进去以后还是cur种

*******************************************************************************

代码：

    int numDecodings(const string &s) {
        if (s.empty() || s[0] == '0') return 0;
        int prev = 0;
        int cur = 1;
        // 长度为n 的字符串，有n+1 个阶梯
        for (size_t i = 1; i <= s.size(); ++i) {
            if (s[i-1] == '0') cur = 0;
            if (i < 2 || !(s[i - 2] == '1' ||
                    (s[i - 2] == '2' && s[i - 1] <= '6')))
                prev = 0;
            int tmp = cur;
            cur = prev + cur;
            prev = tmp;
        }
        return cur;
    }