[TLE]: Got TLE when implemented strncmp


  • 3
    W

    My initial design passed OJ. However, after I implemented a strncmp function myself, I got TLE error. Even tried the strncmp.c source code from gcc-4.2, still got TLE error. Do not understand why strncmp in library used by leetcode is much more efficient.

    Initial code which has passed OJ:

    class Solution {
    public:
    	char *strStr(char *haystack, char *needle) {
    		if (!needle || !haystack) return NULL;
    		if (!(*needle)) return haystack;
    		char *cur = needle;
    		size_t len=0;
    		while (*cur++) len++;
    		while (strncmp(haystack, needle, len))
    			if (!*haystack++) return NULL;
    		return haystack;
    	}
    };
    

    After replace strncmp by mystrncmp, got TLE:

    int mystrncmp(const char *s1, const char *s2, register size_t n){
    	register unsigned char u1, u2;
    	while (n-- > 0){
    		u1 = (unsigned char)*s1++;
    		u2 = (unsigned char)*s2++;
    		if (u1 != u2) return 1;
    		if (u1 == '\0') return 0;
    	}
    	return 0;
    }

  • 2

    The library that is linked to your code could be optimized, while your code is not.

    EDIT:
    As a fun exercise, could you run some performance test using the two versions of your code and update your findings in your question post?

    1. For the first run, compile your code without the optimize flag and time both versions. You should find that version 1 (which uses the system library) is faster.

    2. Now compile your code using the optimize flag -O3. Both versions should be equally fast.


  • 0
    W

    I agree, and I assume this optimization is done by code structure, nothing related to the compiler. Then the question is how to improve the "mystrncmp". As I mentioned, this function is borrowed from Gcc-4.2 library. Thanks.


  • 0

    Yes, the code is exactly the same. But during the linking step, the compiler links the optimized system library to your code, so operations in the system library are faster. In LeetCode OJ, the g++ compiler compiles your code without any optimization, so operations in your code is a little slower, sounds right?


  • 0
    W

    Got it. Appreciate for your reply.


  • 0
    P

    Is this problem supposed to be solvable using strncmp?


  • 0

    No, it is not. in fact, it should TLE using strncmp. But somehow it is able to squeeze by the time limit.


  • 0
    P

    If we are not supposed to solve this using KMP and we could not solve it using strncmp, what should we do?


  • 0
    W

    Exactly, as I suggested in another thread, need to consider to break this strStr problem into two problems. The second problem (strStr II) can add a complexity constraint. Such that the 1st problem can be solved by brute force, while 2nd problem needs to be solved by other more efficient solutions, like KMP.


  • 0

    Sorry for the misunderstanding. You should be able to solve this using the brute force solution. The strncmp solution misses the optimization when the input string is 'aaaa...a' but the target string is 'aaaa...b'.


Log in to reply
 

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