0028-find-the-index-of-the-first-occurrence-in-a-string¶

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.

Example 1:

Input: haystack = "sadbutsad", needle = "sad"
Output: 0
Explanation: "sad" occurs at index 0 and 6.
The first occurrence is at index 0, so we return 0.

Example 2:

Input: haystack = "leetcode", needle = "leeto"
Output: -1
Explanation: "leeto" did not occur in "leetcode", so we return -1.

Constraints:

1 <= haystack.length, needle.length <= 10⁴
haystack and needle consist of only lowercase English characters.

Solution(Python)¶

class Solution:
    def strStr(self, haystack: str, needle: str) -> int:
        # take two pointers i  and j one at haystack and one at needle
        #  iterate i...h
        #     if match found i == needle[0]
        #         j = 1...n
        #           exit early on mismatch
        #         if j == n
        #            return j
        #   return -1
        # dryrun
        #  haystack = "sadbutsad", needle = "sad"
        #  h = 9 n = 3
        #  needle[0] = s
        #  i = 0:  s == s true
        #       j = 1 k = 1 a == a
        #       j = 2 k = 2 d == d
        #      j == n-1
        #          return i
        h = len(haystack)
        n = len(needle)
        for i in range(h):
            if haystack[i] == needle[0]:
                j =  1 
                k = i + 1
                while j < n and k < h and haystack[k] == needle[j]:
                    j += 1
                    k+=1
                if j == n:
                    return i
        return -1
        