0ms C++ solution, bits >96% of submissions


  • 1
    E

    The idea is to use dynamic programming approach and identify a few key cases:
    case-1: when there is no way to decode;
    case-2: when S_i=S_i-2
    case-3: when S_i=S_i-1
    case-4: when S_i=S_i-2 + S_i-1.
    I used an additional array, but the code ca be easily modified to avoid any arrays.

        int numDecodings(string s) {
            int s_size=s.size();
            if(s_size<1) return 0;
            int i=0;
            while(s[i]=='0') i++;
            if(i>0) return 0; // cannot be decoded
            i=s_size-1;
            while(s[i]=='0') i--;
            if(s_size-1-i>1) return 0; // cannot be decoded;
            vector<int> sum(s_size,0);
            sum[0]=1;
            if(s[1]=='0' && (s[0]=='0' || (s[0]-'0')>2)) return 0;
            sum[1]= (s[1]-'0')>0 && (10*(s[0]-'0')+(s[1]-'0'))<=26 ? 2 : 1;
            int pair=0;
            for(int i=2; i<s_size; i++)
            {
                if(s[i]=='0' && (s[i-1]=='0' || (s[i-1]-'0')>2)) return 0; // cannot be decoded
                pair=10*(s[i-1]-'0')+(s[i]-'0');
                if(pair==10 || pair==20) 
                {
                    sum[i]=sum[i-2];
                    continue;
                }
                if(pair>26 || s[i-1]=='0')
                {
                    sum[i]=sum[i-1];
                    continue;    
                }
                sum[i]=sum[i-1]+sum[i-2];
            }
            return sum[s_size-1];
        }
    

Log in to reply
 

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