strStr.md

Implement strStr()

• Return the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack.

• Answer Case

haystack = "hello", needle = "ll"  -> Output: 2

haystack = "aaaaa", needle = "bba"  -> Output: -1

Solution

def strStr(haystack: str, needle: str) -> int:
    # null check
    if (haystack == "" and needle == "") or needle == "":
        return 0
    elif haystack == "":
        return -1

    split_result = haystack.split(needle)
    if split_result[0] == haystack:
        return -1
    elif split_result[0] != haystack:
        return len(split_result[0])

def strStr2(haystack: str, needle: str) -> int:
    return haystack.find(needle)

def strStr3(haystack: str, needle: str) -> int:
    if needle == "":
        return 0
    elif needle in haystack:
        return haystack.index(needle)
    else:
        return -1

def strStr4(haystack: str, needle: str) -> int:
    m, n = len(needle), len(haystack)
    for i in range(n - m + 1):
        for j in range(m):
            if haystack[i + j] != needle[j]:
                break
        else:
            return i
    return -1

def strStr5(haystack: str, needle: str) -> int:
    h, n = len(haystack), len(needle)
    if (h == 0 and n == 0) or n == 0:
        return 0
    elif h == 0 or n > h:
        return -1

    for i in range(h - n + 1):
        if haystack[i:i + n] == needle:
            return i
    return -1

Performance Comparison:

• Test case

n = "ME3"
h = ("AM2CIK4DJCED" * 13312444) + n + ("KDM1EKE" * 100)

• Result summary

Methods	Call count	Call method	Time
strStr	2	split, len	49ms
strStr2	1	find	26ms
strStr3	1	index	53ms
strStr4	1	len	31042ms
strStr5	1	len	9676ms

☕ 더 빠른 알고리즘을 알려주신분께는 Coffee를 사드립니다. (카카오톡 선물하기)