leetcode91. 解码方法

解码方法

一条包含字母 A-Z 的消息通过以下方式进行了编码：

‘A’ -> 1
‘B’ -> 2
…
‘Z’ -> 26

给定一个只包含数字的非空字符串，请计算解码方法的总数。

示例 1:

输入: “12”
输出: 2
解释: 它可以解码为 “AB”（1 2）或者 “L”（12）。

示例 2:

输入: “226”
输出: 3
解释: 它可以解码为 “BZ” (2 26), “VF” (22 6), 或者 “BBF” (2 2 6) 。

思路

1.递归回溯
2.费波纳希

目前均超时，需要优化，参考爬楼梯

实现

递归回溯

class Solution {
public:
    int numDecodings(string s) {
        int res = 0;
        func(res, s, 0);
        return res;
        
    }
    void func(int &res, string s, int start) {
        if (start > s.size()) {
            return;
        }
        if (start == s.size() - 2) {
            if (s[start] == '1' || (s[start] == '2' && s[s.size() - 1] <= '6')) {
                res++;
            }
        }
        if (start == s.size() - 1 && s[s.size() - 1] != '0') {
            res++;
        }
        if (start < s.size()) {
            if (s[start] == '0') {
                    return;
            }
            func(res, s, start + 1);
            if (start + 1 < s.size()) {
                if (s[start] < '2' || (s[start] == '2' && s[start + 1] <= '6')) {
                    func(res, s, start + 2);
                }
            }
        }
    }
};

费波纳希

class Solution {
public:
    int numDecodings(string s) {
      if (s.size() == 1) {
          if (s == "0") {
              return 0;
          } else {
              return 1;
          }
      } 
      
    if (s.size() == 2) {
        if (s[0] == '1') {
             if (s[1] != '0') {
                return 2;
            } else {
                return 1;
            }
        }
        if (s[0] == '2') {
            if (s[1] == '0') {
                return 1;
            } else if (s[1] < '7') {
                return 2;
            } else {
                return 1;
            }
        }
        if (s[0] > '2') {
            if (s[1] == '0') {
                return 0;
            } else {
                return 1;
            }
        }

         
     } 
      if (s[0] == '0') {
          return 0;
      }
      
      if (s[0] == '1' || (s[0] == '2' && s[1] < '7')) {
          return numDecodings(s.substr(1, s.size() - 1)) + numDecodings(s.substr(2, s.size() - 2));
      }  
      return numDecodings(s.substr(1, s.size() - 1));
    }
};