Leetcode 28 - Implement strStr(): question

Question

I am experiencing a bug in my submissions for Leetcode 28 that has thus far eluded me. My code works for most test cases but I am getting hung up on scenarios such as haystack = "mississippi", needle = "issip".

I have tried debugging and found that the entire haystack string is iterated through and it is returning -1 or not found. The substring length it is finding at each occurrence of 'i' is 4, 1, 1.

int strStr(string haystack, string needle) {
        if (needle.empty()) {
            return 0;
        }
        if (haystack.empty() && !needle.empty()) {
            return -1;
        }
        int i = 0, j = 0, ans = 0;
        for (i; i < haystack.length(); i++) {
            if (haystack[i] == needle[0]) {
                j = 0;
                ans = i;
                for (j; j < needle.length(); j++) {
                    /*
                    if (haystack[i++] == needle[j]) {
                        continue;
                    }
                    else {
                        break;
                    }
                    */
                    if (haystack[i++] != needle[j]) {
                        break;
                    }
                }
                if (j == needle.length()) {
                    return ans;
                }
            }
            if (j == needle.length()) {
            return ans;
            }
        }
        return -1;
    }

Input: "mississippi", "issip" Output: -1 (ans = 10, j = 1)

Answer 1

The problem is that you modify i in

if (haystack[i++] != needle[j]) {

Thus preventing a second potential match from being explored. Try

if (haystack[i + j] != needle[j]) {

and fix any knock-on issues. I expect it to work as-is, though.