LintCode-解码方法

512. 解码方法

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

'A' -> 1
'B' -> 2
...
'Z' -> 26

现在给你一个加密过后的消息，问有几种解码的方式

样例

给你的消息为12，有两种方式解码 AB(12) 或者 L(12). 所以返回 2

标签

动态规划
字符串处理

---

很阴的一道题，前后都是坑。

第一眼看上去就是第i个字符位置的解码方式数n[i]为n[i-1]+n[i-2]或n[i]=n[i-1]，分别是当前位置i和i-1能组成10~26的情况和不能的情况。
但有几种特殊情况要考虑：
1、0的前面不为1或2，结果为0；
2、输入“0”的结果也是0；
3、10和20时也只有一种情况，因此只有11~19和21~26可以n[i-1]+n[i-2]；
4、若当前位的后一位为0，则当前位必须为1或2，且只能n[i]=n[i-1]，否则无法解码，结果为0。

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.length()==0) return 0;
        s.insert(0,"0");//dp从第一位开始算起，在第0位插入一个0，则遇到输入“0”时会判断到“00”而判断为无法解码，返回0.
        vector<int> n;
        n.push_back(1);//作为-1位的填充
        n.push_back(1);//第0位，除输入“0”以外，必有一种解码情况
        for(int i=1;i<s.length();i++)
        {
            if(s[i]=='0' && (s[i-1]=='0' || s[i-1]>='3')) return 0;
            if((s[i-1]=='2'&& s[i]<='6' && s[i]>='1' || s[i-1]=='1' && s[i]!='0') && (i+1==s.length() || s[i+1]!='0'))
            {
                n.push_back(n[i]+n[i-1]);
            }
            else
            {
                n.push_back(n[i]);
            }
        }
        return n.back();
    }
};