91. Decode Ways

A message containing letters fromA-Zis 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.

S: DP O(n)

ways[i]表示到i截至的字符串有多少解码方法

分类讨论：

1. 当前数字为0，要么前一个数字为1或2，此时ways[i] = ways[i-2]，要么invalid
2. 当前数字不为0，且前一个数和当前数字的组合在11 - 26的区间内 ways[i] = ways[i-2]+ways[i-1]
3. 其他情况只能当前数字单独解码ways[i] = ways[i-1]

因为ways[i]只与ways[i-1] ways[i-2]有关，可用滚动数组优化

    int numDecodings(string s) {
       int n = s.size();
       if (n == 0 || s[0] == '0') {
           return 0;
       }
       vector<int> ways(2, 1);
       for (int i = 2; i <= n; ++i) {
           if (s[i - 1] == '0') {
               if (s[i - 2] != '1' && s[i - 2] != '2') {
                    return 0;
               } else {
                   ways[i % 2] = ways[(i - 2) % 2];
               }
           } else if ((s[i - 2] == '1'|| (s[i - 2] == '2' && s[i - 1] <= '6'))) {
               ways[i % 2] = ways[(i - 2) % 2] + ways[(i - 1) % 2];
           } else {
               ways[i % 2] = ways[(i - 1) % 2];
           }
       }
       return ways[n % 2];
    }