A 2ms C solution


  • 0
    G
    int strStr(char* haystack, char* needle) {
        int needleLength = strlen(needle) + 1;
        int hayStackLength = strlen(haystack) + 1;
        int hayStackOriginalLength = hayStackLength;
        if (needleLength == 1) {
            return 0;
        }
        for (int i = 0; i < hayStackOriginalLength; i++, hayStackLength--) {
           if (needleLength > hayStackLength) {
                return -1;
            }
            for (int j = i, needleIndex = 0; j < i + needleLength; j++, needleIndex++) {
                if (needleIndex == needleLength - 1) {
                    return i;
                }
                if (needle[needleIndex] != haystack[j]) {
                    break;
                }
            }
        }
        return -1;
    }
    

    The outer loop iterates along the haystack, checking every time whether the effective size (i.e. remaining, unsearched space) is even large enough to contain the needle. Every time a letter is eliminated, that effective size shrinks. This allows us to eliminate cases like the "aaaaaaaa....aaaa", "aaaaa...aaab" quickly.


Log in to reply
 

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