Find the Index of the First Occurrence in a String easy

Problem Statement

Find the index of the first occurrence of needle in haystack.

If needle is an empty string, return 0. If needle is not part of haystack, return -1.

Example 1:

Input: haystack = "hello", needle = "ll"
Output: 2

Example 2:

Input: haystack = "aaaaa", needle = "bba"
Output: -1

Steps

1. Handle Empty Needle: If the needle is empty, return 0 as per the problem statement.

2. Iterate Through Haystack: Use a loop to iterate through the haystack string.

3. Check for Needle: In each iteration, check if the substring of haystack starting at the current index and having the length of needle is equal to needle. We use haystack.substring(i, i + needle.length()) to extract this substring.

4. Return Index: If a match is found, return the current index i.

5. Return -1: If the loop completes without finding a match, return -1.

Explanation

The solution uses a straightforward approach. It iterates through the haystack string, checking at each position whether the next needle.length() characters match the needle. The substring method is used for efficient substring extraction. The use of a loop ensures that we examine every possible starting position for the needle within the haystack.

Code

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;
    }
}

Complexity

• Time Complexity: O(M*N), where M is the length of haystack and N is the length of needle. In the worst case, we might compare the needle with almost every substring of the haystack.

• Space Complexity: O(1). The algorithm uses a constant amount of extra space, regardless of the input size. We are not creating any new data structures whose size depends on the input.