Leetcode.91.Decode Ways

题目

给定一个字符串, 字符串元素都是数字. 数字和字母有对应关系'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();
}

总结

关键是找到规律, 利用缓存和递归思想.