-
Time: O(n)
-
Space: O(n)
class Solution {
// Runtime: 386 ms, faster than 100.00% of Dart online submissions for Push Dominoes.
// Memory Usage: 156.8 MB, less than 100.00% of Dart online submissions for Push Dominoes.
String pushDominoes(String dominoes) {
// splitting the the whole string into a list like each individual character
List<String> finalString = dominoes.split("");
// left falling domino
int L = -1;
// right falling domino
int R = -1;
// looping through the length off the dominoes
for (int i = 0; i <= dominoes.length; ++i)
// if the i same as the dominos length OR smae as the individual character or the splitting list
// of spited list as above assuming from right size
if (i == dominoes.length || finalString[i] == 'R') {
// if the left is greater than the right while right side is less than the individual character
if (L < R) while (R < i) finalString[R++] = 'R';
// than we will give the order to push from the right side
// and our right side is will be equal to the character because we pushed so it's value will be changing
R = i;
// else if the individual character is same aas from the left
} else if (finalString[i] == 'L') {
// assuming the right side is less than left or left and right is a negative value
if (R < L || L == -1 && R == -1) {
// we will push the trigger from the left side
if (L == -1 && R == -1) ++L;
// assuming the left is less than the each character
// so we will increment it at the point of splitting string
while (L < i) finalString[L++] = 'L';
} else {
// if it's not the case
// than defining the left and right sides
int l = R + 1;
int r = i - 1;
// assuming that the left is less than right
while (l < r) {
// increment from the left side by triggering from the right side
// because the left value will increase as the right value decrease
finalString[l++] = 'R';
finalString[r--] = 'L';
}
}
// assigning the left value to the character
L = i;
}
// as a result we will return the resulting string and and join it to make it one single string
return finalString.join();
}
}class Solution {
// Runtime: 407 ms, faster than 100.00% of Dart online submissions for Push Dominoes.
// Memory Usage: 157.4 MB, less than 100.00% of Dart online submissions for Push Dominoes.
String pushDominoes(String dominoes) {
// splitting the string into individual character
List<String> s = dominoes.split("");
// length of our whole string
int n = dominoes.length;
// lift side of the dominoes - holing the how many dominoes available on the left
List<int> left = List.filled(n, 0);
// right side of the dominoes - holing the how many dominoes available on the right
List<int> right = List.filled(n, 0);
// total sum value of both right and left - holing the how many dominoes available on both side
List<int> sum = List.filled(n, 0);
//R command from left to right
int command = 0;
// looping through the whole length - if the length is less than each character
for (int i = 0; i < n; i++) {
if (dominoes[i] == 'R')
// our command will be from right side and assign the vle to i
command = n;
else if (dominoes[i] == 'L')
command = 0;
else if (dominoes[i] == '.') command = max(command - 1, 0);
right[i] = command;
}
int p = 0;
for (int i = n - 1; i >= 0; i--, p++) {
if (dominoes[i] == 'L')
command = n;
else if (dominoes[i] == 'R')
command = 0;
else if (dominoes[i] == '.') command = max(command - 1, 0);
left[i] = command * (-1);
}
for (int i = 0; i < n; i++) {
sum[i] = right[i] + left[i];
if (sum[i] == 0)
s[i] = '.';
else if (sum[i] > 0)
s[i] = 'R';
else
s[i] = 'L';
}
return s.join();
}
}class Solution {
// Runtime: 538 ms, faster than 100.00% of Dart online submissions for Push Dominoes.
// Memory Usage: 154.9 MB, less than 100.00% of Dart online submissions for Push Dominoes.
String pushDominoes(String dominoes) {
List<String> d = dominoes.split("");
// l is the left pointer
int l = 0, n = dominoes.length;
// r is the right pointer
for (int r = 0; r < n; r++) {
if (d[r] == '.') {
// case 1. meeting `.`, then skip it
continue;
} else if ((d[r] == d[l]) || (d[l] == '.' && d[r] == 'L')) {
// case 2. both end is equal, i.e. d[r] == d[l]
// then fill all the dots between both end
// e.g. L....L -> LLLLLL
// e.g. R....R -> RRRRRR
// case 2.1 if the left end is . and the right end is L,
// i.e. d[l] == '.' && d[r] == 'L'
// then we need to fill them from `l` to `r` in this case
for (int k = l; k < r; k++) d[k] = d[r];
} else if (d[l] == 'L' && d[r] == 'R') {
// case 3. left end is L and right end is R
// e.g. L.....R
// then do nothing
} else if (d[l] == 'R' && d[r] == 'L') {
// case 4. left end is R and right end is L
// if we have odd number of dots between them (let's say m dots),
// then we can only add (m / 2) Ls and (m / 2) Rs.
// p.s `/` here is integer division. e.g. 3 / 2 = 1
// e.g. R...L -> RR.LL
// if we have even number of dots between them (let's say m dots),
// then we can only add (m / 2) Ls and (m / 2) Rs.
// e.g. R....L -> RRRLLL
int m = (r - l - 1) ~/ 2;
for (int k = 1; k <= m; k++) {
d[r - k] = 'L';
d[l + k] = 'R';
}
}
// update left pointer
l = r;
}
// case 5. if the left dominoes is `R`, then fill all 'R' till the end
// e.g. LL.R. -> LL.RR
if (d[l] == 'R') for (int k = l; k < n; k++) d[k] = 'R';
return d.join();
}
}