Find The Index Of The First Occurrence In A String - Leetcode Solution

Problem Statement:

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

Example:

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

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

Solution:

The problem can be solved using the brute-force approach where we iterate through haystack and compare the substring of the same length as the needle to the needle. When we find a match we return the starting index of the match. If we don’t find any match, we return -1.

Algorithm:

1. Check the base cases. If the needle is empty return 0. If the length of the haystack is less than the length of needle, return -1.

2. Iterate through the haystack with a loop until haystack length minus needle length. For each iteration, take a substring of the same length as the needle and compare it to needle.

3. If the current substring matches the needle, return the starting index of the match.

4. If we do not find any match, return -1.

Time Complexity: O(n^2) [n is the length of the haystack]

Code:

class Solution: def strStr(self, haystack: str, needle: str) -> int:

    if not needle:
        return 0
    
    h_len = len(haystack)
    n_len = len(needle)
    
    if h_len < n_len:
        return -1
    
    for i in range(h_len - n_len + 1):
        if haystack[i:i + n_len] == needle:
            return i
        
    return -1

Conclusion:

The problem can be solved using the brute-force approach where we iterate through haystack and compare the substring of the same length as the needle to the needle. When we find a match we return the starting index of the match. If we don’t find any match, we return -1.

1