What's the difference between this two Solutions ???? Why one is AC but the other is not??


  • 0
    L

    Solution 1: Time Limit Exceeded

    class Solution {
    public:
    	char *strStr(char *haystack, char *needle) {
    		for(int i = 0; haystack[i] != '\0'; ++i) {
    			int t = i, j;
    			for(j = 0; haystack[t] != '\0' && needle[j] != '\0'; ++j, ++t) {
    				if(haystack[t] != needle[j]) break;
    			}
    			if(needle[j] == '\0') return haystack+i;
    		}
    		return NULL;
    	}
    };
    

    Solution 2: AC

    class Solution {
    public:
        char *strStr(char *haystack, char *needle) {
            int i = 0, j = 0;
            while(haystack[i] != '\0' && needle[j] != '\0') {
                if(haystack[i] == needle[j])
                    ++i, ++j;
                else 
                    i = i-j+1, j = 0;
            }
            return needle[j] == '\0' ? haystack+(i-j) : NULL;
        }
    };

  • 1
    W

    Think about this case
    "aaaaaa.........a","aaaaaa......ab"
    the two parameters both are n length strings
    In the solution 1,the time is O(n*n)
    but in the solution 2, the time is O(n)
    so when you find out the the remaining string in haystack is shorter than needle,you could return NULL directly.


Log in to reply
 

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