FazBrowse GitHub Viewer | Trending | | Home

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

LeetCode-Solutions/Python/flip-game.py at master · pythonpeixun/LeetCode-Solutions · GitHub

32 lines (27 loc) · 950 Bytes

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

# Time: O(c * n + n) = O(n * (c+1))

# Space: O(n)

class Solution(object):

def generatePossibleNextMoves(self, s):

"""

:type s: str

:rtype: List[str]

"""

res = []

i, n = 0, len(s) - 1

while i < n: # O(n) time

if s[i] == '+':

while i < n and s[i+1] == '+': # O(c) time

res.append(s[:i] + '--' + s[i+2:]) # O(n) time and space

i += 1

i += 1

return res

# Time: O(c * m * n + n) = O(c * n + n), where m = 2 in this question

# Space: O(n)

# This solution compares O(m) = O(2) times for two consecutive "+", where m is length of the pattern

class Solution2(object):

def generatePossibleNextMoves(self, s):

"""

:type s: str

:rtype: List[str]

"""

return [s[:i] + "--" + s[i+2:] for i in xrange(len(s) - 1) if s[i:i+2] == "++"]

Back | FazBrowse Home | New Git URL