SRM 587, D2, 250-Pointer (InsertZ)
James S. Plank
Sat Jul 20 11:11:41 EDT 2019
In case Topcoder's servers are down
(Please use the workflow in the problem Cryptography).
Here is a summary of the problem:
- You are given two strings, init and goal.
- init does not contain the character 'z'
- Your goal is to transform init into goal, and the only thing that you
are allowed to do is insert the character 'z' into init. You are
allowed to do that as many times as you want.
- Return "Yes" if it is possible to transform
init into goal in this manner, and
"No" if it is impossible.
- Topcoder constrains the strings to be between 1 and 50 characters, but I am going
to constrain them to be between 1 and 100,000 characters.
The examples
| Example |
init |
goal |
Answer |
| 0 |
"fox" |
"foxz" |
"Yes" |
| 1 |
"fox" |
"zfzoxzz" |
"Yes" |
| 2 |
"foon" |
"foon" |
"Yes" |
| 3 |
"topcoder" |
"zopzoder" |
"No" |
| 4 |
"aaaaaaaaaa" |
"a" |
"No" |
| 5 |
"mvixrdnrpxowkasufnvxaq" |
"mvizzxzzzrdzznzrpxozzwzzkazzzszzuzzfnvxzzzazzq" |
"Yes" |
| 6 |
"opdlfmvuicjsierjowdvnx" |
"zzopzdlfmvzuicjzzsizzeijzowvznxzz" |
"No" |
Testing yourself
I have a shell script
tests.sh, that you can use to test your program. When you
run tests.sh, your answer should be identical to
answers.txt. The shell script should take under a second.
Hints
Try this on your own before reading further.
The low success rate to this problem most likely comes from being lured into thinking
about it in the way that the problem is described -- trying to insert z's into init
so that it matches goal.
Since init doesn't contain any z's initially, you can solve the problem by removing
z's from goal, and then seeing if it matches init.
Now, you don't want to actually remove z's from goal (for example, by using
the erase() method on the string). That would make your
solution O(n2). Instead, create a new string by traversing goal,
and calling push_back() on the new string whenever you encounter a non-z
character in goal. There's a nice, simple, two-line, O(n) solution!