91. Decode Ways

Let dp[i] be the number of decoded ways at position i.
So there are 4 cases:
Case1: s[i] is in ['1', '6'] and s[i-1] is either '1' or '2', then dp[i] = dp[i-1] + dp[i-2].
Case2: s[i] is in ['7', '9'], then dp[i] = dp[i-1].
Case3: s[i] is '0' and s[i-1] is either '1' or '2', then dp[i] = dp[i-2].
Case4: s[i] is '0' and s[i-1] is neither '1' nor '2', then no way to decode.

1:  class Solution {  
2:  public:  
3:    int numDecodings(string s) {  
4:      int n = s.size();  
5:      if (n == 0) return 0;  
6:      if (n == 1) return isValid(s[0]) ? 1 : 0;  
7:      vector<int> dp(n, 0);  
8:      dp[0] = isValid(s[0]) ? 1 : 0;  
9:      if (!isValid(s[1]) && !isValid(s[0], s[1])) return 0;  
10:      dp[1] = isValid(s[0], s[1]) && isValid(s[1]) ? dp[0] + 1 : dp[0];  
11:      for (int i = 2; i < s.size(); i++) {  
12:        if (!isValid(s[i]) && !isValid(s[i-1], s[i])) return 0;  
13:        else if (!isValid(s[i]) && isValid(s[i-1], s[i])) dp[i] = dp[i-2];  
14:        else if (isValid(s[i]) && !isValid(s[i-1], s[i])) dp[i] = dp[i-1];  
15:        else dp[i] = dp[i-1] + dp[i-2];  
16:      }  
17:      return dp[n-1];  
18:    }  
19:    bool isValid(char c) {  
20:      return c != '0';  
21:    }  
22:    bool isValid(char c1, char c2) {  
23:      return c1 == '1' || (c1 == '2' && c2 <= '6');  
24:    }  
25:  };