Leetcode 28: Find the Index of the First Occurrence in a String

 

1. Problem Statement (Simple Explanation):

You are given two strings:

• haystack: the main string

• needle: the substring to search for

Return:

• The index of the first occurrence of needle in haystack.

• If needle is not part of haystack, return -1.

Indexing is 0-based.

2. Examples:

Example 1:

Input:

haystack = "sadbutsad"

needle   = "sad"

Occurrences of "sad":

• At index 0: "sad"butsad

• At index 6: sadb ut"sad"

First occurrence is at index 0.

Output: 0

Example 2:

Input:

haystack = "leetcode"

needle   = "leeto"

"leeto" does not appear in "leetcode".

Output: -1

Constraints:

• 1 <= haystack.length, needle.length <= 104

• Both strings consist of only lowercase English letters.

3. Approach – Simple Sliding Window (Brute Force, O(n·m)):

Given constraints up to 104, a straightforward O(n·m) solution is acceptable.

Let:

• n = len(haystack)

• m = len(needle)

We check all possible starting indices i in haystack where needle might fit:

• Valid start positions: i from 0 to n - m.

For each i, check if:

• haystack[i .. i+m-1] == needle[0 .. m-1]

• If yes, return i.

• If none matches, return -1.

Edge Cases:

• If needle is longer than haystack (m > n): it cannot occur → return -1.

• (In some variations, if needle is empty, they return 0, but here constraints say length ≥ 1, so no need.)

Pseudo-code:

Complexity:

• Time: O(n-m) in worst case.

• Space: O(1) extra.

• For n, m ≤ 104, this is fine in practice.

4. Java code:

5. C code:

6. C++ code:

7. Python code:

(Here we leverage Python slicing for clarity; under the hood it’s similar to the inner loop.)

8. JavaScript code: