Implement strStr()

easy string substring search

Problem

Implement strStr(). Return the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack.

Inputhaystack = "sadbutsad", needle = "sad"

Output0

"sad" appears at index 0 and again at 6; the first occurrence wins.

haystack

needle

def str_str(haystack, needle):
    n, m = len(haystack), len(needle)
    if m == 0:
        return 0
    for i in range(n - m + 1):
        j = 0
        while j < m and haystack[i + j] == needle[j]:
            j += 1
        if j == m:
            return i
    return -1

function strStr(haystack, needle) {
  const n = haystack.length, m = needle.length;
  if (m === 0) return 0;
  for (let i = 0; i <= n - m; i++) {
    let j = 0;
    while (j < m && haystack[i + j] === needle[j]) j++;
    if (j === m) return i;
  }
  return -1;
}

class Solution {
    public int strStr(String haystack, String needle) {
        int n = haystack.length(), m = needle.length();
        if (m == 0) return 0;
        for (int i = 0; i <= n - m; i++) {
            int j = 0;
            while (j < m && haystack.charAt(i + j) == needle.charAt(j)) j++;
            if (j == m) return i;
        }
        return -1;
    }
}

int strStr(string haystack, string needle) {
    int n = haystack.size(), m = needle.size();
    if (m == 0) return 0;
    for (int i = 0; i <= n - m; i++) {
        int j = 0;
        while (j < m && haystack[i + j] == needle[j]) j++;
        if (j == m) return i;
    }
    return -1;
}

Explanation

We want the first place where needle shows up inside haystack. The straightforward way is to try lining up the needle at every possible starting position and check whether it matches there.

The outer loop slides a window: for each start i from 0 up to n - m, we compare the needle character by character. The inner loop advances j as long as haystack[i + j] == needle[j]. If j reaches m, the whole needle matched, so we return i.

If a mismatch happens partway, we stop, slide the window one step right, and try again. If no start ever works, we return -1.

Example: haystack = "sadbutsad", needle = "sad". At i = 0 the first three characters are s, a, d — a full match — so we return 0 immediately, even though sad also appears later at index 6.

In the worst case each of the roughly n − m + 1 windows compares up to m characters, which is where the time bound comes from.

Time: O((n − m + 1) · m) Space: O(1)