2296. Text Editor

Design a Text Editor

此题就把 Cursor看成楚河汉界

Cursor左是红帅区 Cursor右是黑将区

双方 分别是后段和前段 贴著Cursor 因此

Cursor 左边红帅区用LIFO的栈

Cursor 右边黑将区用能头部安插和弹出的Deque

这样Cursor无论往哪移 滑多少

都能轻松调度字符往来栈和Deque

要实现的方法们

addText(string text)

整个text加入Cursor左边的栈

时间复杂度：$O(|\text{text}|)$

deleteText(int k)

从Cursor左边的栈顶删除min(k, len(stack))个字符

最后要回传的实际删除次数 自然是min(k, len(stack))

时间复杂度：$O(k)$

cursorLeft(int k)

Cursor往左移$k$个位置 就是楚河汉界往红帅区压缩

Cursor左栈顶附近的字符 势必成为右Deque头附近的字符

因此把Cursor左边栈顶的min(k, len(stack))个字符

依次弹出栈顶 加入Cursor右边的Deque头

弹好后 再到Cursor左的栈顶

从此往左数min(10, len(stack))个字符 切下子串传回去

时间复杂度：$O(k)$

cursorRight(int k)

Cursor往右移$k$个位置 就是楚河汉界往黑将区压缩

Cursor右Deque头附近的字符 势必成为左栈顶附近的字符

因此把Cursor右边Deque头部的min(k, len(Deque))个字符

依次弹出Deque 加入Cursor左边的栈顶

弹好后 再到Cursor左的栈顶

从此往左数min(10, len(stack))个字符 切下子串传回去

时间复杂度：$O(k)$

空间复杂度就是$O(n)$ $n$代表Cursor两边的字符总数

C++

#include <deque>
#include <string>
#include <vector>
using namespace std;

class TextEditor // LeetCode Q.2296.
{
private:
    deque<char> cursorLeftSide, cursorRightSide;

    string sliceCursorLeftTail() {
        string text = "";

        int startIdx = 0;
        if (cursorLeftSide.size() > 10)
            startIdx += cursorLeftSide.size() - 10;

        for (int idx = startIdx; idx < cursorLeftSide.size(); idx++)
            text += cursorLeftSide[idx];

        return text;
    }

public:
    TextEditor() {}

    void addText(string text) {
        for (const auto& letter : text)
            cursorLeftSide.push_back(letter);
    }

    int deleteText(int k) {
        int deletionsCount = cursorLeftSide.size();
        if (k < deletionsCount)
            deletionsCount = k;

        while (k > 0 && !cursorLeftSide.empty()) {
            cursorLeftSide.pop_back();
            k--;
        }

        return deletionsCount;
    }

    string cursorLeft(int k) {
        while (k > 0 && !cursorLeftSide.empty()) {
            char letter = cursorLeftSide.back();
            cursorRightSide.push_front(letter);
            cursorLeftSide.pop_back();
            k--;
        }

        return sliceCursorLeftTail();
    }

    string cursorRight(int k) {
        while (k > 0 && !cursorRightSide.empty()) {
            char letter = cursorRightSide.front();
            cursorLeftSide.push_back(letter);
            cursorRightSide.pop_front();
            k--;
        }

        return sliceCursorLeftTail();
    }
};

Python

from collections import deque


class TextEditor:  # LeetCode Q.2296.
    def __init__(self) -> None:
        self.cursor_left_side: deque[str] = deque([])
        self.cursor_right_side: deque[str] = deque([])

    def _slice_cursor_left_tail(self) -> str:        
        start_idx = max(0, len(self.cursor_left_side) - 10)

        text = ""
        for idx in range(start_idx, len(self.cursor_left_side)):
            text += self.cursor_left_side[idx]

        return text

    def add_text(self, text: str) -> None:
        self.cursor_left_side.extend(list(text))

    def delete_text(self, k: int) -> int:
        deletions_count = min(k, len(self.cursor_left_side))

        while k > 0 and self.cursor_left_side:
            self.cursor_left_side.pop()
            k -= 1
        
        return deletions_count

    def cursor_left(self, k: int) -> str:
        while k > 0 and self.cursor_left_side:
            char = self.cursor_left_side.pop()
            self.cursor_right_side.appendleft(char)
            k -= 1
        
        return self._slice_cursor_left_tail()

    def cursor_right(self, k: int) -> str:
        while k > 0 and self.cursor_right_side:
            char = self.cursor_right_side.popleft()
            self.cursor_left_side.append(char)
            k -= 1
        
        return self._slice_cursor_left_tail()