[Leetcode] 28. Find the Index of the First Occurrence in a String

Table of Contents

Description

Given two strings needle and haystack, return the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack.

Example 1:

Input: haystack = "sadbutsad", needle = "sad"
Output: 0
Explanation: needle occurs at index 0 and 6.
The first occurrence is at index 0, so we return 0.

Example 2:

Input: haystack = "leetcode", needle = "leeto"
Output: -1
Explanation: leeto did not occur in leetcode, so we return -1.

Constraints:

• $1 \leq \text{haystack.length}, \text{needle.length} \leq 10^4$
• haystack and needle consist of only lowercase English letters.

Approach

The problem can be solved using a simple linear search. We can iterate through the haystack string and check if the substring starting from the current index matches the needle. If it does, we return the current index. If we reach the end of the haystack without finding a match, we return -1.

Solution

/**
 * @param {string} haystack
 * @param {string} needle
 * @return {number}
 */
var strStr = function (haystack, needle) {
  // Iterate while a full needle could fit
  for (let i = 0; i < haystack.length; i++) {
    const c = haystack[i];

    // Full comparison only when first char lines up
    if (haystack.slice(i, i + needle.length) === needle) return i;
  }
  // No match found
  return -1;
};

Complexity Analysis

Time Complexity

The time complexity is $O(n \cdot m)$, where $n$ is the length of haystack and $m$ is the length of needle. In the worst case, we may need to check every character in haystack for a match with needle, leading to a quadratic time complexity.

Space Complexity

The space complexity is $O(1)$, as we are using a constant amount of extra space for variables and do not require any additional data structures that grow with the input size.