-
Notifications
You must be signed in to change notification settings - Fork 17
/
implement-strstr.py
43 lines (35 loc) · 1.37 KB
/
implement-strstr.py
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
class Solution(object):
def strStr(self, haystack, needle):
"""
:type haystack: str
:type needle: str
:rtype: int
"""
haystack_length = len(haystack)
needle_length = len(needle)
needle_shift = 0
haystack_pos = 0
if needle_length > 0:
while haystack_pos < haystack_length:
if haystack[haystack_pos] == needle[needle_shift]:
needle_shift += 1
haystack_pos += 1
if needle_shift == needle_length:
return haystack_pos - needle_length
else:
haystack_pos -= needle_shift - 1
needle_shift = 0
else:
return 0
return -1
solution = Solution()
assert solution.strStr(haystack="", needle="") == 0
assert solution.strStr(haystack="", needle="ll") == -1
assert solution.strStr(haystack="tset", needle="") == 0
assert solution.strStr(haystack="ll", needle="ll") == 0
assert solution.strStr(haystack="llll", needle="ll") == 0
assert solution.strStr(haystack="hello", needle="ll") == 2
assert solution.strStr(haystack="aaaaa", needle="bba") == -1
assert solution.strStr(haystack="hell", needle="ll") == 2
assert solution.strStr(haystack="helloll", needle="ll") == 2
assert solution.strStr(haystack="mississippi", needle="issip") == 4