Approach #1: Adjacent Symbols [Accepted]
Between every group of vertical dominoes (
'.'), we have up to two non-vertical dominoes bordering this group. Since additional dominoes outside this group do not affect the outcome, we can analyze these situations individually: there are 9 of them (as the border could be empty). Actually, if we border the dominoes by
'R', there are only 4 cases. We'll write new letters between these symbols depending on each case.
Continuing our explanation, we analyze cases:
If we have say
"A....B", where A = B, then we should write
If we have
"R....L", then we will write
"RRR.LLL"if we have an odd number of dots. If the initial symbols are at positions
j, we can check our distance
j-kto decide at position
kwhether to write
(If we have
"L....R"we don't do anything. We can skip this case.)
- Time and Space Complexity: , where is the length of
Approach #2: Calculate Force [Accepted]
We can calculate the net force applied on every domino. The forces we care about are how close a domino is to a leftward
'R', and to a rightward
'L': the closer we are, the stronger the force.
Scanning from left to right, our force decays by 1 every iteration, and resets to
N if we meet an
'R', so that
force[i] is higher (than
force[j]) if and only if
dominoes[i] is closer (looking leftward) to
Similarly, scanning from right to left, we can find the force going rightward (closeness to
For some domino
answer[i], if the forces are equal, then the answer is
'.'. Otherwise, the answer is implied by whichever force is stronger.
Here is a worked example on the string
S = 'R.R...L': We find the force going from left to right is
[7, 6, 7, 6, 5, 4, 0]. The force going from right to left is
[0, 0, 0, -4, -5, -6, -7]. Combining them (taking their vector addition), the combined force is
[7, 6, 7, 2, 0, -2, -7], for a final answer of
- Time and Space Complexity: .
Analysis written by: @awice.