LeetCode Problem

Problem 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.

Examples

Input: hello, ll
Output: 2

Input: aaaaa, bba
Output: -1

Input: mississippi,issip
Output: 4

Constraints

1 <= haystack.length, needle.length <= 10^4
haystack and needle consist of only lowercase English letters.

Follow-up

Approach to Solve

Use a sliding window approach to check for the first occurrence of needle in haystack.

Code Implementation

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

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

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

Explanation

This solution uses a sliding window approach to check for the first occurrence of needle in haystack. Here's a detailed explanation of the algorithm:

Check if needle is empty: If the needle is empty, return 0.
Iterate through the haystack: Use a loop to iterate through the haystack from the start to the position where the last character of the needle would fit.
Compare substrings: For each position in the haystack, extract a substring of the same length as the needle and compare it with the needle.
Return the index: If a match is found, return the current index. If no match is found after the loop, return -1.

This approach ensures that the entire haystack is scanned, and the first occurrence of the needle is found if it exists.

Time Complexity: O(n * m), where n is the length of the haystack and m is the length of the needle. In the worst case, the algorithm may need to compare every substring of length m in the haystack. Space Complexity: O(1), as we only use a constant amount of extra space for the loop index and substring extraction.

Complexity

Time Complexity: O(n * m)
Space Complexity: O(1)

LeetSolved

Find the Index of the First Occurrence in a String