Implementation of strStr()

Question

Return the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack. We will return 0 when needle is an empty string. Example 1: Input: haystack = "hello", needle = "ll" Output: 2

This is my code:

class Solution {
public:
    int strStr(string haystack, string needle) {
        if (needle == "") return 0;
        int i = 0, j = 0, poz = -1;
        if (needle.size() > haystack.size()) return -1;
        while (i < haystack.size() && j < needle.size()) {
            if (haystack[i] == needle[j]) {
                poz = i;
                while (i < haystack.size() && j < needle.size() && haystack[i] == needle[j]) {
                    i++;
                    j++;
                }
                if (j == needle.size()) return poz;
                else {
                    i = poz + 1;
                    j = 0;
                }
            } else i++;
        }
        return -1;
    }
};

But for a test case containing two strings with 5 * 10^4 characters, I get TLE. Can you help me correct my code, please?

Answer 1

2 improvement points in your brute force solution.

1. Instead of finding haystack and needle size every time, find them just once at the very beginning of your code, store both values in 2 variables, then use those variables.
2. While traversing each position of the haystack, check whether the remaining haystack size becomes smaller than needle.

class Solution {
public:
    int strStr(string haystack, string needle) {
        int needleSz = needle.size();
        int haystackSz = haystack.size();
        if (needleSz == 0) return 0;
        if (needleSz > haystackSz) return -1;
        int i = 0, j = 0, poz = -1;

        while (i < haystackSz) {
            if (haystackSz - i < needleSz) return -1;
            if (haystack[i] == needle[j]) {
                poz = i;
                while (i < haystackSz && j < needleSz && haystack[i] == needle[j]) {
                    i++;
                    j++;
                }
                if (j == needleSz) {
                    return poz;
                }
                else {
                    i = poz + 1;
                    j = 0;
                }
            } 
            else i++;
        }
        return -1;
    }
};