91. Decode Ways（重要）

​​A-Z​​

'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"​​

​​Subscribe​​ to see which companies asked this question

这题不难，但要注意的细节很多。

1.以0开头的非法；

2.如果s[i]=='0',且s[i-1]=='1'或'2'，dp[i]=dp[i-2];

3.否则，如果s[i - 1] == '1',dp[i]=dp[i-1]+dp[i-2];

     如果s[i] >= '0'&&s[i] <= '6'&&s[i - 1] == '2'，dp[i]=dp[i-1]+dp[i-2];

    否则，dp[i]=dp[i-1];

class Solution {
public:
  int numDecodings(string s) {
    if (s.empty()||s[0]=='0') return 0;
    
    int num2 = 1;
    int num1 = 1;
    int num = 1;

    for (int i = 1; i < s.size(); i++){
      if (s[i] == '0'){
        if (s[i - 1] == '1' || s[i - 1] == '2'){
          num = num2;
        }
        else{
          return 0;
        }
      }
      else{
        if (s[i - 1] == '1'){
          num = num1 + num2;
        }
        else if (s[i] >= '0'&&s[i] <= '6'&&s[i - 1] == '2'){
          num = num1 + num2;
        }
        else{
          num = num1;
        }
      }
      num2 = num1;
      num1 = num;
    }
    return num;
  }
};