设计一个文本编辑器

难度: Hard

请你设计一个带光标的文本编辑器，它可以实现以下功能：

添加：在光标所在处添加文本。
删除：在光标所在处删除文本（模拟键盘的删除键）。
移动：将光标往左或者往右移动。

当删除文本时，只有光标左边的字符会被删除。光标会留在文本内，也就是说任意时候 0 <= cursor.position <= currentText.length 都成立。

请你实现 TextEditor 类：

TextEditor() 用空文本初始化对象。
void addText(string text) 将 text 添加到光标所在位置。添加完后光标在 text 的右边。
int deleteText(int k) 删除光标左边 k 个字符。返回实际删除的字符数目。
string cursorLeft(int k) 将光标向左移动 k 次。返回移动后光标左边 min(10, len) 个字符，其中 len 是光标左边的字符数目。
string cursorRight(int k) 将光标向右移动 k 次。返回移动后光标左边 min(10, len) 个字符，其中 len 是光标左边的字符数目。

示例 1：

输入：
["TextEditor", "addText", "deleteText", "addText", "cursorRight", "cursorLeft", "deleteText", "cursorLeft", "cursorRight"]
[[], ["leetcode"], [4], ["practice"], [3], [8], [10], [2], [6]]
输出：
[null, null, 4, null, "etpractice", "leet", 4, "", "practi"]

解释：
TextEditor textEditor = new TextEditor(); // 当前 text 为 "|" 。（'|' 字符表示光标）
textEditor.addText("leetcode"); // 当前文本为 "leetcode|" 。
textEditor.deleteText(4); // 返回 4
                          // 当前文本为 "leet|" 。
                          // 删除了 4 个字符。
textEditor.addText("practice"); // 当前文本为 "leetpractice|" 。
textEditor.cursorRight(3); // 返回 "etpractice"
                           // 当前文本为 "leetpractice|". 
                           // 光标无法移动到文本以外，所以无法移动。
                           // "etpractice" 是光标左边的 10 个字符。
textEditor.cursorLeft(8); // 返回 "leet"
                          // 当前文本为 "leet|practice" 。
                          // "leet" 是光标左边的 min(10, 4) = 4 个字符。
textEditor.deleteText(10); // 返回 4
                           // 当前文本为 "|practice" 。
                           // 只有 4 个字符被删除了。
textEditor.cursorLeft(2); // 返回 ""
                          // 当前文本为 "|practice" 。
                          // 光标无法移动到文本以外，所以无法移动。
                          // "" 是光标左边的 min(10, 0) = 0 个字符。
textEditor.cursorRight(6); // 返回 "practi"
                           // 当前文本为 "practi|ce" 。
                           // "practi" 是光标左边的 min(10, 6) = 6 个字符。

提示：

1 <= text.length, k <= 40
text 只含有小写英文字母。
调用 addText ，deleteText ，cursorLeft 和 cursorRight 的总次数不超过 2 * 10⁴ 次。

进阶：你能设计并实现一个每次调用时间复杂度为 O(k) 的解决方案吗？

Submission

运行时间: 221 ms

内存: 34.8 MB

class TextEditor:

    def __init__(self):
        self.left, self.right = [], []

    def addText(self, text: str) -> None:
        self.left.extend(text)

    def deleteText(self, k: int) -> int:
        k0 = k
        while k and self.left:
            self.left.pop()
            k -= 1
        return k0 - k

    def text(self):
        return ''.join(self.left[-10:])

    def cursorLeft(self, k: int) -> str:
        while k and self.left:
            self.right.append(self.left.pop())
            k -= 1
        return self.text()


    def cursorRight(self, k: int) -> str:
        while k and self.right:
            self.left.append(self.right.pop())
            k -= 1
        return self.text()


# Your TextEditor object will be instantiated and called as such:
# obj = TextEditor()
# obj.addText(text)
# param_2 = obj.deleteText(k)
# param_3 = obj.cursorLeft(k)
# param_4 = obj.cursorRight(k)

Explain

这个题解使用了两个栈，left和right，来模拟文本编辑器中的光标位置。left栈存储光标左边的所有字符，而right栈存储光标右边的所有字符。当添加文本时，文本被添加到left栈的顶部。当删除文本时，从left栈的顶部移除指定数量的字符。移动光标时，字符会在两个栈之间移动，模拟光标的左右移动。每次操作后，可以通过连接left栈的顶部字符来获取光标左侧的文本。

时间复杂度: O(k)

空间复杂度: O(n)

class TextEditor:

    def __init__(self):
        self.left, self.right = [], []  # 初始化两个栈来存储光标左右的字符

    def addText(self, text: str) -> None:
        self.left.extend(text)  # 向左栈添加文本

    def deleteText(self, k: int) -> int:
        k0 = k
        while k and self.left:
            self.left.pop()  # 从左栈弹出字符
            k -= 1
        return k0 - k  # 返回实际删除的字符数

    def text(self):
        return ''.join(self.left[-10:])  # 获取光标左侧最多10个字符的字符串

    def cursorLeft(self, k: int) -> str:
        while k and self.left:
            self.right.append(self.left.pop())  # 将字符从左栈移动到右栈
            k -= 1
        return self.text()  # 返回移动后光标左侧的文本


    def cursorRight(self, k: int) -> str:
        while k and self.right:
            self.left.append(self.right.pop())  # 将字符从右栈移动到左栈
            k -= 1
        return self.text()  # 返回移动后光标左侧的文本

Explore

使用两个栈来模拟光标位置的主要原因是操作的简便性和效率。在文本编辑器中，光标操作（如移动光标和删除字符）通常涉及到对光标位置前后的字符进行频繁的添加和删除。使用两个栈，一个存储光标左边的字符，另一个存储光标右边的字符，可以非常方便地实现这些操作。例如，移动光标时只需将字符从一个栈移至另一个栈。如果使用链表，则虽然可以实现相似操作，但在特定位置插入和删除字符可能需要更复杂的指针操作和更高的时间成本。使用数组时，插入和删除操作可能需要大量的元素移动，尤其是在数组中间的操作，效率较低。因此，两个栈的使用在此类应用中提供了既简单又高效的解决方案。

题解中已经考虑了这种边界情况。在deleteText方法的实现中，有一个循环会持续从left栈中删除字符，直到删除的字符数达到请求的k个或left栈为空。如果k的值大于left栈的长度，循环会在栈为空时结束。因此，这种情况下会删除left栈中的所有字符，而实际删除的字符数目等于原left栈的长度，这个值会在方法的最后被返回。

是的，题解中已经考虑了这种情况。无论是cursorLeft还是cursorRight方法，都包含一个循环，该循环会持续执行直到移动的步数k为0或相应的栈（left栈或right栈）为空。这意味着如果k的值大于栈的深度，循环会在栈为空时结束，此时不会再有更多的字符可以移动。由此，光标的移动不会超过有效的位置范围。

返回实际删除的字符数目可以为调用者提供重要的反馈信息。在多种情况下，如编程或编辑应用中，知道实际删除了多少字符可能对于进一步的操作决策或错误处理非常有用。例如，在一个自动化的编辑任务中，程序可能需要确认确切删除了多少字符来决定是否需要进行额外的修改或更新其他相关的数据结构。此外，这也可以帮助调试和验证程序的正确性。