91. 解码方法

问题描述

一条包含字母 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) 。

问题分析

如果字符串长度为0或者开头为0,则肯定无法解码，返回0，所以之后开头肯定大于0，所以开头第一个元素已经考虑了，只有一个解码方式，初始化cur=1与pre=1,然后从第二个元素开始遍历：

• 1.遇到s[i]元素为0，考虑之前元素s[i-1]:
  • 1.1 若s[i-1] = 1 或s[i-1] = 2,则只有一种编码方式，所以编码方式总数不变，cur = pre;
  • 1.2 否则是非法编码；

• 2.如果s[i-1] = 1 或者 （s[i-1] = 2 && s[i] < 7)，这时可以两种编码方式(以s[i-1]s[i]一起解码或s[i]单独解码)，cur += pre;否则只有s[i]单独解码，cur不变

  代码

class Solution {
public:
    int numDecodings(string s) {
        int n = s.size();
        if(n == 0) return 0;
        if(s[0] == '0')return 0;//之后s[0]>=1
        int i,ans = 0;
        int cur = 1,pre = 1,tmp;//在第i步，实际cur = dp[i+1],pre = d[i-1],tmp = dp[i]
        for(i = 1; i < n; i++)
        {
            tmp = cur;//因为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] < '7'))
                cur += pre;
            pre = tmp;  
            
        }
        return cur;
    }
};