leetcode-解码方法

点击：题目链接：一条包含字母 A-Z 的消息通过以下映射进行了 编码 ：
‘A’ -> 1
‘B’ -> 2
…
‘Z’ -> 26
要 解码 已编码的消息，所有数字必须基于上述映射的方法，反向映射回字母（可能有多种方法）。例如，”111” 可以将 “1” 中的每个 “1” 映射为 “A” ，从而得到 “AAA” ，或者可以将 “11” 和 “1”（分别为 “K” 和 “A” ）映射为 “KA” 。注意，”06” 不能映射为 “F” ，因为 “6” 和 “06” 不同。
给你一个只含数字的 非空 字符串 num ，请计算并返回 解码 方法的 总数 。
题目数据保证答案肯定是一个 32 位 的整数。

思路

通常情况，判断当前可以解码的个数需要知道上一个字母的解码总数。如果该数为0， 我还需要结合上一个数，若不符合条件，我们就需要直接判断该字符串是不满足条件的。

边界情况，f(-1) = 1, f(0) = 1

• 若为0， 则判断前一个数是否为1和2， 若总数为f(i) = f(i-1)，否则字符串不合格

• 若前一个数为2，则需要需要判断该数是否在1到6，或者前一个数为1，该数无论0到9，若满足条件，则f(i) = f(i-2)+f(i-1)

  • f(i-1) 为分开解码的情况， f(i-2) 为合并后解码的情况

  由于这里只涉及到f(i-1)和f(i-2)， 故我们可以用滚动数组进行替代

  代码

  class Solution {
  public:
  	int numDecodings(string s) {
  		if (s[0] == '0') return 0;
  
  		int pre = 1, cur = 1;
  		for (int i = 1; i < s.size(); ++i) {
  			int temp = cur;
  			if (s[i] == '0') {
  				if (s[i - 1] == '1' || s[i - 1] == '2') cur = pre;
  				else return 0;
  			}
  			else if ((s[i - 1] == '1' || (s[i - 1] == '2') && (s[i] > '0' && s[i] < '7')))
  				cur = cur+pre;
  
  			pre = temp;
  
  		}
  		return cur;
  	}
  };

  复杂度

  时间：O(N), 空间：O（1）