leetcode 91. Decode Ways

Seawolf

1. A message containing letters from A-Z is being encoded to numbers using the following mapping:
   
2. 
   
3. 'A' -> 1
   
4. 'B' -> 2
   
5. ...
   
6. 'Z' -> 26
   
7. Given a non-empty string containing only digits, determine the total number of ways to decode it.
   
8. 
   
9. Example 1:
   
10. 
    
11. Input: "12"
    
12. Output: 2
    
13. Explanation: It could be decoded as "AB" (1 2) or "L" (12).
    
14. Example 2:
    
15. 
    
16. Input: "226"
    
17. Output: 3
    
18. Explanation: It could be decoded as "BZ" (2 26), "VF" (22 6), or "BBF" (2 2 6).

复制代码

dp solution

1. class Solution {
   
2. public:
   
3.     int numDecodings(string s) {
   
4.         
   
5.         if(s.length() == 0 || s[0] == '0') return 0;
   
6.         vector <int> dp(s.length()+1,0);
   
7.         dp[0] = 1;
   
8.         dp[1] = 1;
   
9.         int max1 = 0;
   
10.         for(int i = 2; i <= s.length(); i++){
    
11.             
    
12.             if(s[i-1] >= '1' && s[i-1] < '27'){
    
13.                 dp[i] += dp[i-1];
    
14.             }
    
15.             
    
16.             if(s[i-2] == '1' || (s[i-2] == '2' && s[i-1] >= '0' && s[i-1] <= '6')){
    
17.                 dp[i] += dp[i-2];
    
18.             }
    
19.             
    
20.             
    
21.         }
    
22.         return dp[s.length()];
    
23.     }
    
24. };

复制代码