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
My answer by Python


@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(BA) running time.

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

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

@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.