91. Decode Ways

题目

A message containing letters from A-Z is being encoded to numbers using the following mapping:

‘A’ -> 1
‘B’ -> 2
…
‘Z’ -> 26
Given an encoded message containing digits, determine the total number of ways to decode it.

For example,
Given encoded message “12”, it could be decoded as “AB” (1 2) or “L” (12).

The number of ways decoding “12” is 2.

一个信息包含从A到Z的字母，这个信息按照如下的规则编码成数字：
‘A’ -> 1
‘B’ -> 2
…
‘Z’ -> 26
那么现在给定一个编码数字串，找出有多少种方法来解码。

解题思路

其实这题跟爬楼梯是一样的题目，假设f[i]表示i级台阶有多少种爬法，那么可以得到转移方程f[i] = f[i-1] + f[i-2]，其中f[1]=1,f[2]=2. 这一题的解题思路也是这样的，但是需要考虑’0’这个例外。单个数字’0’是不能够被解码的，因此我们的全部解题思路就是：

如果s[i-1] > ‘0‘，那么加上f[i-1]，否则不加。

如果s[i-2]和s[i-1]组成的数字在1~26之间，那么加上f[i-2]，否则不加。

class Solution {
public:

 bool isValid(char a, char b) {
     if (a != '1' && a != '2')
         return false;
     if (a == '2' && b > '6')
         return false;
     return true;
 }

    int numDecodings(string s) {
        if (s.empty() || s[0] == '0') return 0;
        int n = s.size();
        int f[n] = {
   0};
        f[0] = 1;
        for (int i = 1; i < n; i++) {
            if (s[i] > '0' && s[i] <= '9')
                f[i] += f[i-1];
            if (isValid(s[i-1], s[i]))
                if (i < 2)
                    f[i] += 1;
                else
                    f[i] += f[i-2];
        }
        return f[n-1];
    }
};