Back to solutions

Find The Index of The First Occurrence in a String

EasyArrays

Return the first index where needle occurs in haystack, or -1.

Open problem
Constraints
  • 1 <= |haystack|, |needle| <= 10^4
  • Lowercase English letters

Sliding window compare

Time O(n*m) worst caseSpace O(1)

Try every start index i where needle could still fit. Compare needle against the substring of haystack starting at i character by character; the first index where all characters match is the answer.

Key terms
haystack / needle:
The text being searched and the pattern being searched for.
window:
The length-m slice of haystack currently being compared to needle.
int strStr(const string& haystack, const string& needle) {
    int n = haystack.size(), m = needle.size();
    for (int i = 0; i + m <= n; i++) {
        int j = 0;
        while (j < m && haystack[i + j] == needle[j]) j++;
        if (j == m) return i;
    }
    return -1;
}
Step by step
  1. Loop i from 0 while i + m <= n (needle still fits).
  2. Compare needle[0..m) with haystack[i..i+m) one character at a time.
  3. If all m characters match, return i.
  4. If no start index matches, return -1.