Find the Index of the First Occurrence in a String easy

Problem Statement

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

Clarification:

What should we return when needle is an empty string? This is a great question to ask during an interview.

For the purpose of this problem, we will return 0 when needle is an empty string. This is consistent with the behavior of the C library's strstr() function.

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's clarification.

2. Iterate through Haystack: Iterate through the haystack string using a loop.

3. Compare Substrings: In each iteration, compare a substring of haystack (of the same length as needle) with the needle. We use haystack.Substring(i, needle.Length) to extract the substring.

4. Check for Match: If the substring matches the needle, return the current index i.

5. Handle No Match: If the loop completes without finding a match, return -1.

Explanation

The solution uses a straightforward approach of iterating through the haystack and comparing substrings. The Substring method efficiently extracts the portion of the haystack for comparison. The loop continues until either a match is found or the end of the haystack is reached. Error handling is built-in by returning -1 in the case of no match.

Code

using System;

public class Solution {
    public int StrStr(string haystack, string needle) {
        if (string.IsNullOrEmpty(needle)) {
            return 0;
        }

        for (int i = 0; i <= haystack.Length - needle.Length; i++) {
            if (haystack.Substring(i, needle.Length) == 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 almost all substrings of haystack with needle.

• Space Complexity: O(1). The algorithm uses only a constant amount of extra space. We're not creating any data structures that scale with the input size. The Substring method itself does not create a new string in .NET; it returns a view of the original string.