HackerRank ‘Simple Text Editor’ Solution

H
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:

  1. append(W) – Appends the string W at the end of S.
  2. erase(k) – Erase the last k character of S.
  3. get(k) – Returns the kth character of S.
  4. undo() – Undo the last not previously undone operation of type 1 or 2, so it reverts S to the state before that operation.
Link

Simple Text Editor

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:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
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()

About the author

Add comment

Archives

Categories