# My answer by Python

• ``````class Solution(object):
def strStr(self, haystack, needle):
"""
:type haystack: str
:type needle: str
:rtype: int
"""
for i in range(len(haystack) - len(needle)+1):
if haystack[i:i+len(needle)] == needle:
return i
return -1``````

• elegant solution!

• what's the time complexity?

• @Taroka O(n)

• @Taroka @CeltRay001 The time complexity is definitely not O(n), it is O(n*m).

Since checking haystack[i:i+len(needle)] == needle is O(m) done O(n) times.

n - length of haystack m - length of needle

• @Taroka Time complexity is O(M * N), where M is the length of haystack and N is the length of the needle.
Note that slicing a list using [A:B] operator leads O(B-A) running time.

• This solution seems not consider the case when input str is none.

• What a wonderful idea! Thanks for sharing!

@charleszhou327 I think it does since when i = 0 and len(needle) = 0, return 0

• funny, KMP is slow than this O(m*n ) solution：

``````    def strStr_KMP(self, t, p):
pnext, i, j = self.gen_pnext(p), 0, 0
n, m = len(t), len(p)
while j < n and i < m:
if i == -1 or t[j] == p[i]:
j, i = j + 1, i + 1
else:
i = pnext[i]
if i == m:
return j - i
return -1

def gen_pnext(self, p):
i, k, m = 0, -1, len(p)
pnext = [-1] * m
while i < m - 1:
if k == -1 or p[i] == p[k]:
i, k = i + 1, k + 1
if p[i] == p[k]:
pnext[i] = pnext[k]
else:
pnext[i] = k
else:
k = pnext[k]
return pnext
``````

• Wow, the Same!

• ``````def strStr(self, haystack, needle):
"""
:type haystack: str
:type needle: str
:rtype: int
"""
if len(haystack) < len(needle): # early termination
return -1
if not needle:
return 0

i = j = 0
while j < len(needle) and i < len(haystack):
if haystack[i] != needle[j]:
i = i - j + 1
j = 0
continue
i += 1
j += 1
return i - j if j == len(needle) else -1``````

• only 1 line code
return haystack.find(needle)

• This post is deleted!

• good, got it!

• though I wonder what if we just use...

``````return haystack.find(needle)
``````

And also "two pointers" is not applied.

• @ChangYuXiaoXiao said in My answer by Python:
sorry, can you explan this line that how do you think out is for me?

len(haystack) - len(needle)+1
I'm not very cleary about it.

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