Concise 9 line C++ solution with explanation


  • -4
    L

    A standard DP problem. The DP formula can be opt[i] = opt[i-1]+1+opt[i-2]+1 and handle some special cases. BTW, I believe the specs of this problem need to be refined. Because it didn't say how to handle '0'. It may be skipped or taken as invalid. For the "01" case, I originally think the answer should be 1, but it is 0, so I have to deduce the requirement.

    class Solution {
    public:
        int numDecodings(string s) 
        {
            if(s.size()==0||s[0]=='0') return 0;
            vector<int> opt(s.size(),0);
            for(int i = 0;i<s.size();i++) {
                if(s[i]!='0')
                    opt[i]=i>=1?opt[i-1]:0+1;
                if(i>=1&&(s[i-1]=='1'||(s[i-1]=='2'&&s[i]<='6')))
                    opt[i] += i>=2?opt[i-2]:0+1;
            }
            return opt[s.size()-1];
        }
    };

  • 0
    W

    are you sure your code is accepted?At first ,O(n) space is not needed.second,in some cases like "70",I think we should return 0.forgive my poor English.


Log in to reply
 

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