My in-place 0S divide and conquer C solution


  • 1
    D

    For example, {1212}, divided as {12 | 12}, the number of decode ways is {12} * {12} and plus {1}*{21}{2}

    int rnd(char *str, int s, int e)
    {
        if(s >= e){
                return 1;
        }
        if(e - s == 1){
                int c = e;
                if((str[c-1] == '1' && str[c] != '0')|| (str[c-1] == '2' && str[c] < '7' && str[c] > '0')){
                        return 2;
                }else{
                        return 1;
                }
        }
    
        int c = (s + e) / 2;
        if(str[c] == '0'){
                c++;
        }
        int p = rnd(str, s, c-1) * rnd(str, c, e);
        if((str[c-1] == '1' || (str[c-1] == '2' && str[c] < '7' && str[c] > '0')) && (c < e && str[c+1] != '0')){
                p = p +  rnd(str, s, c-2) *  rnd(str, c+1, e);
        }
        return p;
    }
    int numDecodings(char* s) {
        if(s == NULL ||strlen(s) == 0|| *s == '0'){
                return 0;
        }
        int i = 0;
        int len = strlen(s);
        int ret = 1;
        if(s[0] <= '0' || s[0] > '9'){
                return 0;
        }
        int last = 0;
        for(i = 1; i < len; i++){
                if(s[i] < '0' || s[i] > '9'){
                        return 0;
                }
                if(s[i] == '0' && (s[i-1] == '0' || s[i-1] > '2')){
                        return 0;
                }
        }
        ret = rnd(s, 0, strlen(s)-1);
        return ret;
     }

Log in to reply
 

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