forked from Kyrylo-Ktl/LeetCode-Solutions
-
Notifications
You must be signed in to change notification settings - Fork 0
/
Push Dominoes.py
66 lines (56 loc) · 1.4 KB
/
Push Dominoes.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
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
class Solution:
"""
Time: O(n)
Memory: O(n)
"""
def pushDominoes(self, dominoes: str) -> str:
n = len(dominoes)
force = [0] * n
f = 0
for i in range(n):
if dominoes[i] == 'R':
f = n
elif dominoes[i] == 'L':
f = 0
else:
f = max(f - 1, 0)
force[i] += f
f = 0
for i in reversed(range(n)):
if dominoes[i] == 'L':
f = n
elif dominoes[i] == 'R':
f = 0
else:
f = max(f - 1, 0)
force[i] -= f
return ''.join('.' if f == 0 else 'R' if f > 0 else 'L' for f in force)
class Solution:
"""
Time: O(n)
Memory: O(n)
"""
def pushDominoes(self, dominoes: str) -> str:
n = len(dominoes)
force = [0] * n
f = 0
for i in range(n):
f = {
'L': 0,
'R': n,
'.': max(f - 1, 0),
}[dominoes[i]]
force[i] += f
f = 0
for i in range(n - 1, -1, -1):
f = {
'L': n,
'R': 0,
'.': max(f - 1, 0),
}[dominoes[i]]
force[i] -= f
return ''.join({
f == 0: '.',
f < 0: 'L',
f > 0: 'R',
}[True] for f in force)