Approach #1: Direct [Accepted]
Intuition and Algorithm
We showcase two different approaches. In both approaches, we build some answer string
ans, that starts as
S. Our main motivation in these approaches is to be able to identify and handle when a given replacement operation does nothing.
In Java, the idea is to build an array
match that tells us
match[ix] = j whenever
S[ix] is the head of a successful replacement operation
j: that is, whenever
After, we build the answer using this match array. For each index
S, we can use
match to check whether
S[ix] is being replaced or not. We repeatedly either write the next character
S[ix], or groups of characters
targets[match[ix]], depending on the value of
In Python, we sort our replacement jobs
(i, x, y) in reverse order. If
S[i:].startswith(x), then we can replace that section
S[i:i+len(x)] with the target
y. We used a reverse order so that edits to
S do not interfere with the rest of the queries.
Time Complexity: , where is the length of
S, and we have replacement operations. (Our complexity could be faster with a more accurate implementation, but it isn't necessary.)
Space Complexity: , if we consider
targets[i].length <= 100as a constant bound.
Analysis written by: @awice.