838.md

838 Push Dominoes

Description

link

---

Solution : TP

Here is an idea that focus on 'L' and 'R':

        'R......R' => 'RRRRRRRR'
        'R......L' => 'RRRRLLLL' or 'RRRR.LLLL'
        'L......R' => 'L......R'
        'L......L' => 'LLLLLLLL'

just set l,r to record 'X.....X', X in [L, R]

---

Code

Complexity T : O(N) M : O(N)

class Solution:
    def pushDominoes(self, dominoes):
        """
        :type dominoes: str
        :rtype: str
        """
        res = []
        
        dominoes = 'L' + dominoes + 'R'
        
        '''
        Here is another idea that focus on 'L' and 'R'.
        'R......R' => 'RRRRRRRR'
        'R......L' => 'RRRRLLLL' or 'RRRR.LLLL'
        'L......R' => 'L......R'
        'L......L' => 'LLLLLLLL'
        '''
        
        l = 0
        for r in range(1, len(dominoes)):
            if dominoes[r] == '.':
                continue
                
            length = r - l - 1
            if l: res += dominoes[l]
            if dominoes[r] == dominoes[l]:
                res += [dominoes[r]] * (length)
            elif dominoes[l] == 'L' and dominoes[r] == 'R':
                res += (['.'] * length)
            elif dominoes[r] == 'L' and dominoes[l] == 'R':
                res += (['R'] * (length // 2) + ['.'] * (length % 2) + ['L'] * (length // 2))
            l = r
            
        return ''.join(res)