Implement Strstr - revisit it

28. Implement strStr() | Easy

This one says it's easy but the answer acceptance rate is rather low. The solution below is rather slow and inefficient. With large inputs LeetCode outputs time exceeded error. Will revisit later.

class Solution:
    def strStr(self, haystack, needle):
        """
        :type haystack: str
        :type needle: str
        :rtype: int
        """
        # idea 1 - resursive letter checking
        # idea 2 - iterative each letter checking with elimination
        # question - what to return when there is more than one match?
        if len(needle) == 0:
            return 0
        elif len(haystack) == 0:
            return -1
        elif len(needle) > len(haystack):
            return -1
        
    
        lead = [ [1, length, 0, length] for length in range(len(haystack))]
        
        for n in needle:
            for j in range(len(haystack)):
                if lead[j][0] == 1 and \
                    lead[j][1] < len(haystack) and \
                    lead[j][2] < len(needle) and \
                    needle[lead[j][2]] == haystack[lead[j][1]]:
                    lead[j][1] += 1
                    lead[j][2] += 1
                elif lead[j][0]:
                    lead[j][0] = 0
        result = [x[3] for x in lead if x[0] == 1]
        if len(result) == 0:
            return -1
        else:
            return result[0]