C++ DP O(1) space O(N) time


  • 0

    class Solution {
    public:

    int numDecodings(string s) {
        if(s.empty()) return 0;
        
        int len = s.size();
    
        int sec = 1;
        int frst = (s[len-1] != '0')? 1:0;
    
        for(int i = len-2; i >= 0; i--)
        {
            if(s[i] == '0') 
                sec = 0;
            else if(stoi(s.substr(i, 2)) > 26)
                sec = frst;
            else
                sec += frst;
            swap(frst, sec);
        }
        return frst;
    }
    

    };


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.