学步园

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.

思路：

这是一个动态规划的问题。题目一个模糊不清的地方是，”01“是不能按照”1“来解码的，也即不能忽略之前的”0“。考察输入串中第i，i-1，i-2的三个字符。设decode_ways[i]为到第i个字符为止，找到的解码个数，s[i]为输入串中第i个字符。那么s[i-1]和s[i]可以有几种可能：

• s[i]，s[i-1]分别可以解码，同时s[i-1]s[i]组成的二位数也可以解码。这样，decode_ways[i]应该是decode_ways[i-1]和decode_ways[i-2]的和。例如"221"，解码的数字等于”22“解码的数字（多余的1可以单独解码）与”2“解码的数字（多余的”21“也可以单独解码）之和。
• s[i]不能单独解码（为0），那么必须和s[i-1]组成一个部分，decode_ways[i]只能等于decode_ways[i-2]。
• s[i-1]s[i]不能解码，但是s[i]可以解码。那么decode_ways[i-2]将无法贡献，解码的数字decode_ways[i]等于decode_ways[i-1]。
• 其他情况（包括几种不可能存在的情况，如s[i-1]s[i]可以解码但是s[i]，s[i-1]都不可以解码），decode_ways[i]只能等于0。

由此写出状态转移方程和代码。

题解：

class Solution
{
public:
    bool two_valid(char c, char d)
    {
        return c!=0 && c*10+d<=26;
    }

    int numDecodings(string s)
    {
        const int LEN=s.size();
        
        if (LEN==0 || s[0]=='0') return 0;
        if (LEN==1) return 1;
        transform(s.begin(), s.end(), s.begin(), bind2nd(minus<char>(),'0'));
        vector<int> decoding(LEN);
        vector<int> valid(LEN);
        transform(s.begin(), s.end(), valid.begin(), bind2nd(not_equal_to<char>(), 0));

        decoding[0]=valid[0];
        if (two_valid(s[0],s[1]))
            decoding[1]=(valid[1] ? decoding[0]+1 : decoding[0]);
        else
            decoding[1]=(valid[1] ? 1 : 0);

        for(int i=2;i<LEN;++i)
        {
            int k=(valid[i]<<2)+(valid[i-1]<<1)+two_valid(s[i-1],s[i]);
            switch(k)
            {
                case 7:
                    decoding[i]=decoding[i-2]+decoding[i-1];
                    break;
                case 3:
                    decoding[i]=decoding[i-2];
                    break;
                case 4:
                case 6:
                    decoding[i]=decoding[i-1];
                    break;
                default:
                    decoding[i]=0;
                    break;
            }
        }
        return decoding[LEN-1];
    }
};