PROBLEM STATEMENT
You are writing a simple text editor that supports only the following two commands:
"type c" where c is a character: Append character c to the end of the current text.
"undo t" where t is an integer: Undo all operations that were performed in the previous t seconds
in reverse order.
All quotes are for clarity only. The text in the editor is initially empty.
For example, consider the following sequence of commands:
Second 1: type a
Second 2: type b
Second 3: type c
Second 5: undo 3
At the end of second 3, the text is "abc". At second 5, all commands performed in the previous 3
seconds are undone in reverse order. This means 'c' is removed, and then 'b' is removed. The
text becomes just "a".
Note that "undo" commands can also be undone. For example:
Second 1: type a
Second 2: type b
Second 3: undo 2
Second 4: undo 2
After second 2, the text is "ab". After second 3, everything is undone, and the text becomes
empty. At second 4, the previous "undo" is undone, so the text becomes "ab" again. Then, the
"type b" is also undone and the text becomes just "a".
You are given a vector commands and a vector time. Each element of commands is a
single command, and commands[i] is performed at time[i]. The commands are given in chronological
order. Return the text after all the commands are executed.
DEFINITION
Class:Undo
Method:getText
Parameters:vector , vector
Returns:string
Method signature:string getText(vector commands, vector time)
CONSTRAINTS
-commands will contain between 1 and 50 elements, inclusive.
-Each element of commands will be either "type c" where c is a lowercase letter ('a'-'z') or "undo
t" where t is an integer between 1 and 10^9, inclusive, with no leading zeroes (quotes for clarity
only).
-time will contain the same number of elements as commands.
-Each element of time will be between 1 and 10^9, inclusive.
-The elements of time will be in strictly ascending order.
EXAMPLES
0)
{"type a", "type b", "type c", "undo 3"}
{1, 2, 3, 5}
Returns: "a"
The first example from the problem statement.
1)
{"type a", "type b", "undo 2", "undo 2"}
{1,2,3,4}
Returns: "a"
The second example from the problem statement.
2)
{"type a", "undo 1", "undo 1"}
{1,2,3}
Returns: "a"
3)
{"type a", "type b", "type c", "undo 10"}
{1, 2, 3, 1000}
Returns: "abc"
Note that "undo" can undo nothing if it is too late.
4)
{"undo 1"}
{1}
Returns: ""
This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2010, TopCoder, Inc. All rights reserved.