case太蛋疼了。。。。
class Solution {
public:
int numDecodings(string s) {
vector<int> ans(s.size()+1, 0);
if (s.empty()) return 0;
ans[0] = 1;
if (s[0] == '0')
ans[1] = 0;
else
ans[1] = 1;
for (int i=2; i<=s.size(); i++) {
int pre = s[i-2]-'0';
int cur = s[i-1]-'0';
int val = pre*10 + cur;
if (cur>=1 && cur<=9)
ans[i] = ans[i-1];
if ((pre != 0) && (val>=1 && val<=26))
ans[i] += ans[i-2];
}
return ans[s.size()];
}
};
发现如果当前字符合法，那么和没有他的时候decode次数一样，相当于一棵tire树每一个链多了一个字母，但链数不变。
如果当前字符和前一个字符的形成的数字在[1,26]那么，需要加上Ways[i-2]的数量，而不能直接等于Ways[i-1] + Ways[i-2]，比如”10“，假设到‘0’了，前面是1，这里是0，
形成的数字是10，范围合法，直接等于1处的合法范围+1（Ways[0]）是不对的，因为0是不合法的，所以不能算Ways[i-1]
哎蛋疼，今天没睡好。现在起床了