Difficulty: Medium
We can split this questions into cases depending on where the .‘s are:
We iterate through the array, and if we see a ”.”, we keep track of the char before the . and char after the .. Then we just change the .‘s based on the above rules.
class Solution(object):
def pushDominoes(self, dominoes):
"""
:type dominoes: str
:rtype: str
"""
# start right
# -> end right -> convert everything to right
# -> end left -> convert half to left
# -> convert half to right
# -> if odd -> middle one stays '-'
# -> EOF -> all right
# start left
# -> end left -> convert everything to left
# -> end right -> everything stays as is
# -> EOF -> leave as is
domino_list = [char for char in dominoes]
curr = "L"
startIndex = -1
for i in range(len(domino_list)):
char = domino_list[i]
if char == ".":
if startIndex == -1:
startIndex = i
else:
if startIndex != -1:
if curr == "R":
if char == "R":
for index in range(startIndex, i):
domino_list[index] = "R"
else:
middle_diff = (i - startIndex) // 2 # 3 4 5 6 7
offset = 1 if (i - startIndex) % 2 == 1 else 0
# 8 - 3 = 5 //
for index in range(startIndex, startIndex + middle_diff):
domino_list[index] = "R"
for index in range(startIndex + middle_diff + offset, i):
domino_list[index] = "L"
if curr == "L":
if char == "L":
for index in range(startIndex, i):
domino_list[index] = "L"
startIndex = -1
curr = char
if startIndex != -1 and curr == "R":
for i in range(startIndex, len(domino_list)):
domino_list[i] = "R"
return "".join(domino_list)Time Complexity:
O(n)Space Complexity:
O(n)Time Taken:
28m 16s