two ways, recursion, much easier to think of but time limited; dynamic programming, the faster and better one


  • 3
    Z

    recursion:

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

    dynamic programming:

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

Log in to reply
 

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