A Short C++ DP O(1) space O(n) time solution for reference


  • 2
    Q
    class Solution {
    public:
        int numDecodings(string s) {
            if (s.empty()) return 0;
            int t1=s.back()=='0'?0:1, t2=1, rv=t1;
            for (int i=s.size()-2; i>=0; i--) {
                if (s[i]=='0') rv=0;
                else rv=t1+(atoi(s.substr(i, 2).c_str())<=26?t2:0);
                t2=t1;
                t1=rv;
            }
            return rv;
        }
    };

Log in to reply
 

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