91. Decode Ways

發表於 | 分類於

problem

solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    int numDecodings(string s) {
        if(s.empty() || s[0] == '0') return 0;
        int n = s.size();
        vector<int> dp(n+1,0);
        dp[0] = 1;
        for(int i=1;i<n+1;++i){
            dp[i] = (s[i-1] == '0') ?0:dp[i-1];
            if(i>1 && (s[i-2] == '1' || (s[i-2] == '2' && s[i-1] <='6')) )dp[i] +=dp[i-2];
            
        }
        return dp[n];
        
    }
};

analysis

  • time complexity O(n)
  • space complexity O(1)