FazBrowse GitHub Viewer | Trending | | Home

Tools: [Download Repo ZIP] [View Raw Code] [Original HTTPS Page]

LeetCode-Solutions/Python/implement-strstr.py at master · pythonpeixun/LeetCode-Solutions · GitHub

54 lines (46 loc) · 1.3 KB

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

# Time: O(n + k)

# Space: O(k)

class Solution(object):

def strStr(self, haystack, needle):

"""

:type haystack: str

:type needle: str

:rtype: int

"""

if not needle:

return 0

return self.KMP(haystack, needle)

def KMP(self, text, pattern):

prefix = self.getPrefix(pattern)

j = -1

for i in xrange(len(text)):

while j > -1 and pattern[j + 1] != text[i]:

j = prefix[j]

if pattern[j + 1] == text[i]:

j += 1

if j == len(pattern) - 1:

return i - j

return -1

def getPrefix(self, pattern):

prefix = [-1] * len(pattern)

j = -1

for i in xrange(1, len(pattern)):

while j > -1 and pattern[j + 1] != pattern[i]:

j = prefix[j]

if pattern[j + 1] == pattern[i]:

j += 1

prefix[i] = j

return prefix

# Time: O(n * k)

# Space: O(k)

class Solution2(object):

def strStr(self, haystack, needle):

"""

:type haystack: str

:type needle: str

:rtype: int

"""

for i in xrange(len(haystack) - len(needle) + 1):

if haystack[i : i + len(needle)] == needle:

return i

return -1

Back | FazBrowse Home | New Git URL