My DP solution in C code, 4ms


  • 0
    X
    int test(char *s, int len) {
    	char real[len+1];
    	int t;
    	memcpy(real, s, len);
    	real[len] = '\0';
    	if (real[0] == '0') {
    		return 0;
    	}
    	t = atoi(real);
    	if (t >= 1 && t <= 26){
    		return 1;
            }
    	return 0;
    }
    
    int numDecodings(char* s) {
        int len;
        int idx;
        char *p;
        if (s == NULL) return 0;
        if ((len=strlen(s)) == 1) {
            return test(s, 1);
        } else if ( len == 0) {
            return 0;
        } else if (len == 2) {
            return test(s, 1) * test(s+1, 1) + test(s, 2);
        }
        int store[len];
        store[0] = numDecodings(s+len-1);
        store[1] = numDecodings(s+len-2);
        for(idx = 2, p = s+len-3; idx < len; idx++,p--) {
            store[idx] = test(p, 1) * store[idx-1] + test(p, 2) * store[idx-2];
        }
        return store[len-1];
    }

Log in to reply
 

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