1

I am writing a simple code in Python that returns the start index of a substring. I used two pointers in my original approach, but it took too long failed the test case.

def strStr(haystack, needle):
    if needle == "":
        return 0
    for count in range(len(haystack)):
        if len(needle) > len(haystack)-count:
            break
        if haystack[count] == needle[0]:
            for count2 in range(len(needle)):
                if needle[count2] != haystack[count+count2]:
                    break
                if count2+1 == len(needle):
                    return count
    return -1

I then found another solution online. This passes the test just fine:

def strStr(haystack, needle):
    if needle == "":
        return 0
    for i, c in enumerate(haystack):
        if len(haystack) < i + len(needle):
            break
        elif haystack[i:i+len(needle)] == needle:
            return i
    return -1

During my search, I saw another language (I think Java) passed the test just fine using the two pointers approach. Why does the first example take longer than the second in Python?

DaramG K
  • 31
  • 3
  • 2
    you code has 2 nested for, while the latter has only 1. – Lei Yang Jul 15 '21 at 02:55
  • Yes, but that for loop is equivalent to the elif statement in the second query. The two queries are both O(len(haystack) * len(needle)) == O(N*M). – DaramG K Jul 16 '21 at 02:40
  • https://stackoverflow.com/questions/49950747/why-is-string-comparison-so-fast-in-python I'll take that as answer to my question. – DaramG K Jul 16 '21 at 02:43

0 Answers0