838.md

838. Push Dominoes

Solution 1 (time O(n^2m+nlog(n)), space O(n))

class Solution(object):
    def pushDominoes(self, dominoes):
        """
        :type dominoes: str
        :rtype: str
        """
        s = list(dominoes)
        n = len(s)
        p1 = 0
        left = 'L'
        while p1 < n:
            p2 = p1
            while p2 < n and s[p2] == '.':
                p2 += 1
            if p2 < n:
                right = s[p2]
            else:
                right = "R"
            if left == right:
                cur_left = p1
                cur_right = p2 - 1
                while cur_left <= cur_right:
                    s[cur_left] = left
                    cur_left += 1
            elif left == "R" and right == "L":
                cur_left = p1
                cur_right = p2 - 1
                while cur_left < cur_right:
                    s[cur_left] = "R"
                    s[cur_right] = "L"
                    cur_left += 1
                    cur_right -= 1
            left = right
            p1 = p2 + 1
        return "".join(s)