[Leetcode] 2296. Design a Text Editor

2296. Design a Text Editor

Design a text editor with a cursor that can do the following:

Add text to where the cursor is.

Delete text from where the cursor is (simulating the backspace key).

Move the cursor either left or right.

When deleting text, only characters to the left of the cursor will be deleted. The cursor will also remain within the actual text and cannot be moved beyond it. More formally, we have that 0 <= cursor.position <= currentText.length always holds.

Implement the TextEditor class:

TextEditor() Initializes the object with empty text.

void addText(string text) Appends text to where the cursor is. The cursor ends to the right of text.

int deleteText(int k) Deletes k characters to the left of the cursor. Returns the number of characters actually deleted.

string cursorLeft(int k) Moves the cursor to the left k times. Returns the last min(10, len) characters to the left of the cursor, where len is the number of characters to the left of the cursor.

string cursorRight(int k) Moves the cursor to the right k times. Returns the last min(10, len) characters to the left of the cursor, where len is the number of characters to the left of the cursor.

Constraints:

1 <= text.length, k <= 40

text consists of lowercase English letters.

At most 2 * 10^4 calls in total will be made to addText, deleteText, cursorLeft and cursorRight.

Analysis:

This question is labeled as hard in Leetcode, but the logic is quick straightforward. The only problem is the efficiency. 

If we use a string and an index for the cursor position, then we will see TLE or MLE.

One neat method is to use two stacks, one is the left stack and the other is right stack. 

For add, we just push the new string into left stack;

for delete, we just pop up the chars from the left stack;

for leftMove, we just pop out k or less (if less than k elements remains) chars from left stack, and push in right stack; then return 10 or less(if less than 10 elements remains) from the left stack;

for rightMore we just need to do the reversed operation as that for the leftMove.

See the code below

class TextEditor {
public:
    TextEditor() {
    }
    
    void addText(string text) {
        for(auto &a : text) lt.push(a);
    }
    
    int deleteText(int k) {
        int res = 0;
        while (lt.size() && k > 0) {
            lt.pop();
            ++res;
            --k;
        }
        // cout << "delet" << endl;
        return res;
    }
    
    string cursorLeft(int k) {
        while(lt.size() && k > 0) {
            auto t = lt.top();
            lt.pop();
            rt.push(t);
            --k;
        }
        return f(lt, 10);
    }
    
    string cursorRight(int k) {
         while(rt.size() && k > 0) {
            auto t = rt.top();
            rt.pop();
            lt.push(t);
            --k;
        }
        return f(lt, 10);
    }
private:
    stack<int> lt, rt;
    string f(stack<int> &sk, int k) {
        string res;
        while(sk.size() && k > 0) {
            res.push_back(sk.top());
            sk.pop();
            --k;
        }
        reverse(res.begin(), res.end());
        for(auto &a : res) sk.push(a);
        return res;
    }
};

/**
 * Your TextEditor object will be instantiated and called as such:
 * TextEditor* obj = new TextEditor();
 * obj->addText(text);
 * int param_2 = obj->deleteText(k);
 * string param_3 = obj->cursorLeft(k);
 * string param_4 = obj->cursorRight(k);
 */