Sharing my solution -using left & right pointers in Python. Best run time:55ms O(m+n)


  • 0
    S

    Best run time- 55 ms.

    class Solution(object):
     
        def strStr(self, haystack, needle):
            n = len(needle)
            m =len(haystack)
            if  n > m:
                return -1
            if ((n==m==0)or (n==0) or (needle == haystack)):
                return 0
            left=0
            right = m-1
            left_found = right_found = -1 
            '''
            if there is more than 1 instance of pattern from left and right 
            Eg:text:'banana', pattern:'na' - can be found at 2,4 indices. But 2 is the preferred solution for this problem
            '''
            while left < right:
                
                if( haystack[left] == needle[0] and ((left+n)<m)): 
                '''check for ith letter from left, if it matches verify the pattern'''
                   if haystack[left:left+n]== needle:
                       left_found= left
                       
                if(haystack[right] == needle[-1] and ((right-n+1)>0)):
                    if haystack[right-n+1:right+1] == needle:
                        right_found= right-n+1
                        
                left += 1
                right -= 1
                if(left_found != -1):  
                    return left_found
       '''There can be more than 1 matched index from the left, gotta return before it gets overwritten. Eg: text: Mississippi ,pattern:issi - found at 1 and 4 indices. Return 1 '''
                    
            if(right_found != -1):
                return right_found
            return -1

Log in to reply
 

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