Short Problem Definition:
In this problem, your task is to implement a simple text editor. Initially, a file contains an empty string S. Your task is to perform Q operations consisting of the following 4 types:
- append(W) - Appends the string W at the end of S.
- erase(k) - Erase the last k character of S.
- get(k) - Returns the kth character of S.
- undo() - Undo the last not previously undone operation of type 1 or 2, so it reverts S to the state before that operation.
Link
Complexity:
time complexity is
space complexity is
Execution:
I maintain two separate stacks. Self.stack represents the current state of the text. I can read data from this stack by indexing it. Self.cmds keeps the history of commands. Each command type knows how to execute itself and how to revert itself.
Solution:
class AppendCmd():
def execute(self, stack, value):
self.length = len(value)
stack.extend(value)
def revert(self, stack):
for _ in xrange(self.length):
stack.pop()
class EraseCmd():
def execute(self, stack, value):
self.text = stack[-value:]
for _ in xrange(value):
stack.pop()
def revert(self, stack):
stack.extend(self.text)
class CustomStack:
def __init__(self):
self.stack = []
self.cmds = []
def push(self, value):
cmd = AppendCmd()
cmd.execute(self.stack, value)
self.cmds.append(cmd)
def pop(self, value):
cmd = EraseCmd()
cmd.execute(self.stack, value)
self.cmds.append(cmd)
def get(self, value):
print self.stack[value]
def revert(self):
cmd = self.cmds.pop()
cmd.revert(self.stack)
def main():
cs = CustomStack()
N = int(raw_input())
for _ in xrange(N):
unknown = raw_input()
command = unknown[0]
if command == '1':
cmd, value = unknown.split()
cs.push(list(value))
elif command == '2':
cmd, value = map(int, unknown.split())
cs.pop(value)
elif command == '3':
cmd, value = map(int, unknown.split())
cs.get(value - 1)
else:
cs.revert()
if __name__ == '__main__':
main()