题目
给定一个字符串, 字符串元素都是数字. 数字和字母有对应关系'A' -> 1, 'B'->2,...,'Z'->26, 求字符串共有多少种解法.
Input: "226"
Output: 3
Input: "12"
Output: 2
解析
数字解析为对应字母, 需要考虑特殊情况0,7,8,9的特殊情况.
类似于斐波那契数列, 递归思想, 需要采用缓存的递归.
思路
int numDecodings(string s) {
if(s.length() == 1) return s[0] != '0';
vector<int> r(s.length(), 0);
r[0] = s[0] != '0';
r[1] = (s[1] != '0' ? r[0] : 0) + (s[0] == '1' || (s[0] == '2' && s[1] < '7') ? 1 : 0);
for(int i = 2; i < s.length(); ++i) {
r[i] = (s[i] != '0' ? r[i-1] : 0) + (s[i-1] == '1' || (s[i-1] == '2' && s[i] < '7') ? r[i-2] : 0);
}
return r.back();
}
总结
关键是找到规律, 利用缓存和递归思想.
