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)