LeetCodeProjectPython/28. Implement strStr().py at master · xulzee/LeetCodeProjectPython · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
# -*- coding: utf-8 -*-
# @Time : 2019/3/1 10:19
# @Author : xulzee
# @Email : xulzee@163.com
# @File : 28. Implement strStr().py
# @Software: PyCharm
fromtypingimportList


classSolution:
defget_next(self, s: str) ->List[int]:
next_list= [-1] *len(s)
i=0
j=-1
whilei<len(s) -1:
ifj==-1ors[i] ==s[j]:
i+=1
j+=1
next_list[i] =j
else:
j=next_list[j]
returnnext_list

defstrStr(self, haystack: str, needle: str) ->int:
next_list=self.get_next(needle)
j=0
i=0
whilei<len(haystack) andj<len(needle):
ifj==-1orhaystack[i] ==needle[j]:
j+=1
i+=1
else:
j=next_list[j]
ifj==len(needle):
returni-j
else:
return-1
defstrStr1(self, haystack, needle):
"""
 :type haystack: str
 :type needle: str
 :rtype: int
 """
ifnotneedle:
return0

len_h=len(haystack)
len_n=len(needle)

foriinrange(len_h):
ifi+len_n>len_h:
return-1

ifhaystack[i] ==needle[0]:
ifhaystack[i:len_n+i] ==needle:
returni

return-1

if__name__=='__main__':
haystack="ababc"
needle="issip"
print(Solution().strStr(haystack, needle))