Editorial for WC '16 Contest 1 J2 - Frankenstein's Monster
Submitting an official solution before solving the problem yourself is a bannable offence.
An important skill in solving problems like this one is interpreting the statement. The most important part of the statement is this:
A "word" is a maximal consecutive sequence of non-period characters in the string. That is, each word is either preceded by a period or is at the start of the string. Similarly, each word is followed by a period or is at the end of the string.
This means that we should replace all substrings Frankenstein
with Frankenstein's.Monster
if and only if one of the following is true:
- it's at the beginning of (always followed by a period, except when it's also at the end of )
- it's both preceded and followed by a period
- it's at the end of (always preceded by a period, except when it's also at the beginning of )
We can solve this by finding all substrings Frankenstein
and checking all these cases. Alternatively, this problem becomes a bit simpler if we start by augmenting the given string, adding one .
to the start and another .
to the end (we just have to remember to remove these at the end before outputting the answer). We then want to replace every occurrence of .Frankenstein.
with .Frankenstein's.monster.
. To find each occurrence, some programming languages provide a built-in function to search for a substring within a string. Alternatively, this can be done by looping over every character in the string and checking if the -character substring starting there is equal to .Frankenstein.
. Once an occurrence is found starting at index , one way to replace it is to replace the whole string with the concatenation of substrings .Frankenstein's.monster.
where is the length of .
Comments