My 9 ms C solution with complexity of O(n) (with clear explanation)


  • 0

    Actually, this is an easy problem. There're just 5 situations we need to take care of.

    1. The length of string is 1, just return false
    2. The length of string is even or dividable by 3
    3. The length of string is even
    4. The length of string is dividable by 3
    5. The length of string is prime

    I defined three functions to solve situation 2, 3, 4 and 5. And the complexity is O(n) at most.
    The complete solution is(the order of these situations matters):

    // judge_even(char*, int)
    bool judge_even(char* str, int len) {
        int i = len / 2;
        int j = 0;
        while(j < i) {
            if(str[j] != str[i+j])
                return false;
            ++j;
        }
        return true;
    }
    
    //judge_db3(char*, int)
    bool judge_odd(char* str, int len) {
        int i = len / 3;
        int j = 2 * i;
        int k = 0;
        while(k < i) {
            if(str[k] != str[i+k] || str[k] != str[j+k])
                return false;
            ++k;
        }
        return true;
    }
    
    //judge_prime(char*, int)
    bool judge_prime(char* str, int len) {
        char pre = str[0];
        int i;
        for(i = 1; i < len; ++i) {
            if(str[i] != pre)
                return false;
            pre = str[i];
        }
        return true;
    }
    
    bool repeatedSubstringPattern(char* str) {
        int len = strlen(str);
        
        if(1 == len) return false;
        
        if(len % 3 == 0 && len % 2 == 0) {
            if(judge_db3(str, len)) return true;
            return judge_even(str, len);
            /* or
             * if(judge_even(str, len)) return true;
             * return judge_db3(str, len);
             */
        }
        
        if(len % 3 == 0) {
            return judge_db3(str, len);
        }
        
        if(len % 2 == 0) {
            return judge_even(str, len);
        }
        
        return judge_prime(str, len);
    }
    

Log in to reply
 

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