838 Push Dominoes

838. Push Dominoes

1. Question

There areNdominoes in a line, and we place each domino vertically upright.

In the beginning, we simultaneously push some of the dominoes either to the left or to the right.

After each second, each domino that is falling to the left pushes the adjacent domino on the left.

Similarly, the dominoes falling to the right push their adjacent dominoes standing on the right.

When a vertical domino has dominoes falling on it from both sides, it stays still due to the balance of the forces.

For the purposes of this question, we will consider that a falling domino expends no additional force to a falling or already fallen domino.

Given a string "S" representing the initial state. S[i] = 'L', if the i-th domino has been pushed to the left;S[i] = 'R', if the i-th domino has been pushed to the right;S[i] = '.', if thei-th domino has not been pushed.

Return a string representing the final state.

Example 1:

Input: 
".L.R...LR..L.."

Output: 
"LL.RR.LLRRLL.."

Example 2:

Input: 
"RR.L"

Output: 
"RR.L"

Explanation: 
The first domino expends no additional force on the second domino.

Note:

1. 0 <= N <= 10^5

2. String dominoescontains only 'L','R'and'.'

2. Implementation

(1) Two Pointer

思路: 根据观察，我们可以发现以下在区间[i,j]的规律:

• 如果dominoes.charAt(i)是R，dominoes.charAt(j)是R, 则[i,j]之间都变成R，同理，当dominioes.charAt(i)是L，dominoes.charAt(j)是L, [i,j]都变成L

• 如果dominoes.charAt(i)是L ,dominoes.charAt(j)是R, 则[i,j]之间不做改变

• 如果dominoes.charAt(i)是R, dominoes.charAt(j)是L, 则[i, j]的前半部分要变成L,后半部分要变成R, 如果[i, j]的长度是奇数，最中间位置一定是'.'

综上，我们可以用一个变量prevR记录目前最近的R的位置，prevR是-1表示当前没有看到R. 当dominoes.charAt(i)是L，如果prevR是-1，则将[prevR + 1, i - 1]之间全变成L, 否则将[prevR + 1, i - 1的前半部分变为R, 后半部分为L, 同时将prevR变为-1, 表示当前区间已经平衡，需要重新找到新的R。当dominoes.charAt(i)是R时，如果prevR不是-1, 则将[prevR + 1, i - 1]都变为R. 最后还要确认prevR是否为-1，如果不是，就将[prevR + 1, dominoes.length - 1]部分都变成R

class Solution {
    public String pushDominoes(String dominoes) {
        if (dominoes == null || dominoes.length() == 0) {
            return dominoes;
        }
        char[] letters = dominoes.toCharArray();
        int prevR = -1;

        for (int i = 0; i < letters.length; i++) {
            if (letters[i] == 'L') {
                if (prevR == -1) {
                    for (int j = i - 1; j >= 0 && letters[j] != 'L'; j--) {
                        letters[j] = 'L';
                    }
                }
                else {
                    int start = prevR + 1;
                    int end = i - 1;
                    while (start < end) {
                        letters[start] = 'R';
                        letters[end] = 'L';
                        ++start;
                        --end;
                    }
                    prevR = -1;
                }

            }
            else if (letters[i] == 'R') {
                if (prevR != -1) {
                    for (int j = i - 1; j > prevR; j--) {
                        letters[j] = 'R';
                    }
                }
                prevR = i;
            }
        }

        if (prevR != -1) {
            for (int i = prevR + 1; i < letters.length; i++) {
                letters[i] = 'R';
            }
        }
        return new String(letters);
    }
}

3. Time & Space Complexity

Two Pointer: 时间复杂度O(n), 空间复杂度O(1)