Push dominoes
September 27, 2022
two-pointersProblem URL: Push dominoes
Any triplet that reaches the state R.L
remains that state permanently. These changes occur to pairs that are not part of an R.L
, R.
-> RR
an .L
-> LL
. To avoid the problem with the R.L
state when we address the R.
-> RR
and .L
-> LL
changes, we replace each R.L
with a dummy string (say, xxx
). Then we perform the R.
-> RR
, .L
-> LL
replacements. Once the described actions are complete and no other replacements are occured, we replace the dummy xxx
string with R.L
and return as result.
class Solution:
def pushDominoes(self, dominoes: str) -> str:
temp = ''
while dominoes != temp:
temp = dominoes
dominoes = dominoes.replace('R.L', 'xxx')
dominoes = dominoes.replace('R.', 'RR')
dominoes = dominoes.replace('.L', 'LL')
return dominoes.replace('xxx', 'R.L')
Time Complexity: O(n^2)
Space Complexity: O(1)