Solution 1 - Brute Force (Sliding Window)

Iterate through the haystack string and at each position, check if the substring of length len(needle) matches the needle. If a match is found, return the starting index. If no match is found after checking all positions, return -1.

TimeComplexity: O((m - n) \cdot n)

SpaceComplexity: O(1)

""" 0028.1 - Find the Index of the First Occurrence in a String - Solution 1 - Brute Force """

#####################################################################################
# Imports
#####################################################################################


#####################################################################################
# Classes
#####################################################################################
class Solution:
    """Solution Class"""

    def strStr(self, haystack: str, needle: str) -> int:
        """Find the index of the first occurrence of needle in haystack"""
        m, n = len(haystack), len(needle)
        for i in range(m - n + 1):
            if haystack[i:i + n] == needle:
                return i
        return -1


#####################################################################################
# Functions
#####################################################################################
def testcase():
    """Test Function"""
    print(Solution().strStr("sadbutsad", "sad"))       # Expected: 0
    print(Solution().strStr("leetcode", "leeto"))      # Expected: -1
    print(Solution().strStr("hello", "ll"))            # Expected: 2
    print(Solution().strStr("a", "a"))                 # Expected: 0


#####################################################################################
# Main
#####################################################################################
if __name__ == "__main__":
    testcase()

Solution 2 - Using Python Built-in `find()`

Leverage Python's built-in str.find() method which returns the lowest index of the substring if found, or -1 if not found. This is the most Pythonic approach.

TimeComplexity: O((m - n) \cdot n)

SpaceComplexity: O(1)

""" 0028.2 - Find the Index of the First Occurrence in a String - Solution 2 - Using find() """

#####################################################################################
# Imports
#####################################################################################


#####################################################################################
# Classes
#####################################################################################
class Solution:
    """Solution Class"""

    def strStr(self, haystack: str, needle: str) -> int:
        """Find the index of the first occurrence of needle in haystack"""
        return haystack.find(needle)


#####################################################################################
# Functions
#####################################################################################
def testcase():
    """Test Function"""
    print(Solution().strStr("sadbutsad", "sad"))       # Expected: 0
    print(Solution().strStr("leetcode", "leeto"))      # Expected: -1
    print(Solution().strStr("hello", "ll"))            # Expected: 2
    print(Solution().strStr("a", "a"))                 # Expected: 0


#####################################################################################
# Main
#####################################################################################
if __name__ == "__main__":
    testcase()

Solution 3 - Character-by-Character Comparison

Instead of using slicing, compare characters one by one. At each starting position in haystack, iterate through needle and compare each character. If all characters match, return the index. This avoids creating substring copies.

TimeComplexity: O((m - n) \cdot n)

SpaceComplexity: O(1)

""" 0028.3 - Find the Index of the First Occurrence in a String - Solution 3 - Char by Char """

#####################################################################################
# Imports
#####################################################################################


#####################################################################################
# Classes
#####################################################################################
class Solution:
    """Solution Class"""

    def strStr(self, haystack: str, needle: str) -> int:
        """Find the index of the first occurrence of needle in haystack"""
        m, n = len(haystack), len(needle)
        for i in range(m - n + 1):
            match = True
            for j in range(n):
                if haystack[i + j] != needle[j]:
                    match = False
                    break
            if match:
                return i
        return -1


#####################################################################################
# Functions
#####################################################################################
def testcase():
    """Test Function"""
    print(Solution().strStr("sadbutsad", "sad"))       # Expected: 0
    print(Solution().strStr("leetcode", "leeto"))      # Expected: -1
    print(Solution().strStr("hello", "ll"))            # Expected: 2
    print(Solution().strStr("a", "a"))                 # Expected: 0


#####################################################################################
# Main
#####################################################################################
if __name__ == "__main__":
    testcase()

0028 - Find the Index of the First Occurrence in a String

Solution 1 - Brute Force (Sliding Window)

Solution 2 - Using Python Built-in find()

Solution 3 - Character-by-Character Comparison

Solution 2 - Using Python Built-in `find()`