Python Solution, O(NM)


  • 1
    L
    def strStr(haystack, needle): # Time: O((N-M) * M), Space: O(1)
        """
        Returns the index of the first occurrence of needle in haystack.
        Or, -1 if needle is not part of haystack.
        
        >>> strStr("hello", "ll")
        2
        >>> strStr("hello", "ee")
        -1
        """
        
        if (needle == ""):
            return 0
        
        needleLen = len(needle)
        
        for n in range(len(haystack) - needleLen + 1): # O(N - M), where N is len(haystack) and M is len(needle)
            if haystack[n : (n+len(needle))] == needle: # O(M) + O(M)
                return n
        return -1
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.