28. Find the Index of the First Occurrence in a String

Intuition

The problem requires finding the first occurrence of the substring needle within the string haystack. If needle is not found in haystack, we return -1.

Approach

1. Edge Case Handling: Check if needle is empty. If it is, return 0 immediately because an empty needle is always found at the beginning of haystack.
2. Iterate Through haystack: Use a loop to iterate through haystack. For each position i in haystack, check if the substring starting at i and of length equal to the length of needle matches needle.
3. Return the Index: If a match is found, return the index i where needle starts in haystack.
4. Return -1 if Not Found: If the loop completes without finding needle, return -1.

Complexity

Time Complexity:

O((n-m+1) * m) where n is the length of haystack and m is the length of needle. The worst-case scenario involves checking all possible substrings of length m in haystack.

Space Complexity:

O(1) extra space, apart from input space.

Code

C++

class Solution {
public:
    int strStr(string haystack, string needle) {
        if (haystack.length() < needle.length()) {
            return -1;}
        for (int i = 0; i <= haystack.length() - needle.length(); i++) {
            if (haystack.substr(i, needle.length()) == needle) {
                return i;
            }}
        return -1;
    }};

Python

class Solution:
    def strStr(self, haystack: str, needle: str) -> int:
        if len(haystack) < len(needle):
            return -1
        for i in range(len(haystack) - len(needle) + 1):
            if haystack[i:i + len(needle)] == needle:
                return i
        return -1

Java

class Solution {
    public int strStr(String haystack, String needle) {
        if (haystack.length() < needle.length()) {
            return -1;
        }
        for (int i = 0; i <= haystack.length() - needle.length(); i++) {
            if (haystack.substring(i, i + needle.length()).equals(needle)) {
                return i;
            }
        }
        return -1;
    }
}

JavaScript

var strStr = function (haystack, needle) {
    if (haystack.length < needle.length) {
        return -1;
    }
    for (let i = 0; i <= haystack.length - needle.length; i++) {
        if (haystack.substring(i, i + needle.length) === needle) {
            return i;
        }
    }
    return -1;
};