1
class Solution:
2
    def pushDominoes(self, dom: str) -> str:
3
        from collections import deque
4

5
        n = len(dom)
6
        d = set()
7
        q = deque()
8
        arr = [0 for i in range(n)]
9
        for i in range(n):
10
            if dom[i] == "L":
11
                arr[i] = -1
12
                d.add(i)
13
                q.append((i, "L"))
14
            if dom[i] == "R":
15
                arr[i] = 1
16
                d.add(i)
17
                q.append((i, "R"))
18
        while q:
19
            t1 = set()
20
            for _ in range(len(q)):
21
                t = q.popleft()
22
                if t[1] == "L":
23
                    if t[0] - 1 >= 0 and t[0] - 1 not in d:
24
                        t1.add(t[0] - 1)
25
                        arr[t[0] - 1] -= 1
26
                else:
27
                    if t[0] + 1 < n and t[0] + 1 not in d:
28
                        t1.add(t[0] + 1)
29
                        arr[t[0] + 1] += 1
30
            for val in t1:
31
                d.add(val)
32
                if arr[val] > 0:
33
                    q.append((val, "R"))
34
                elif arr[val] < 0:
35
                    q.append((val, "L"))
36
        ans = ""
37
        for val in arr:
38
            if val < 0:
39
                ans += "L"
40
            elif val > 0:
41
                ans += "R"
42
            else:
43
                ans += "."
44
        return ans