Hard

题目描述

设计一个带光标的文本编辑器，可以执行以下操作：

  • 在光标处添加文本
  • 从光标处删除文本（模拟退格键）
  • 向左或向右移动光标

删除文本时，只会删除光标左侧的字符。光标始终保持在实际文本范围内，不能移动到文本之外。更正式地说，始终满足 0 <= cursor.position <= currentText.length。

实现 TextEditor 类：

  • TextEditor() 用空文本初始化对象
  • void addText(string text) 在光标处追加文本，光标移动到文本末尾
  • int deleteText(int k) 删除光标左侧的 k 个字符，返回实际删除的字符数
  • string cursorLeft(int k) 将光标向左移动 k 次，返回光标左侧最多 10 个字符
  • string cursorRight(int k) 将光标向右移动 k 次，返回光标左侧最多 10 个字符

示例 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"]

约束条件：

  • 1 <= text.length, k <= 40
  • text 由小写英文字母组成
  • 最多调用 addText、deleteText、cursorLeft 和 cursorRight 共 2 * 10^4 次

进阶： 你能找到每次调用时间复杂度为 O(k) 的解决方案吗？

解题思路

解题思路

这道题的关键是理解光标的概念和如何高效地在任意位置进行插入、删除操作。

方法一：双栈模拟（推荐）

核心思想是将文本分为两部分：

  • 左栈：存储光标左侧的字符，栈顶是光标左侧最近的字符
  • 右栈：存储光标右侧的字符，栈顶是光标右侧最近的字符

这样设计的优势：

  1. 添加文本：直接推入左栈，O(|text|) 时间
  2. 删除文本：从左栈弹出元素，O(k) 时间
  3. 光标移动：在两个栈之间转移元素，O(k) 时间
  4. 获取左侧字符：从左栈顶部取最多10个字符，O(1) 时间

方法二：字符串+位置指针

使用一个字符串存储所有文本，用一个指针记录光标位置。但这种方法在删除和插入时需要移动大量字符，时间复杂度较高。

方法三：双向链表

使用双向链表，光标在两个节点之间。插入删除操作时间复杂度较低，但实现复杂，且获取左侧字符需要遍历。

双栈方法在所有操作上都能达到最优时间复杂度，是最佳选择。

代码实现

class TextEditor {
private:
    string left, right;
    
public:
    TextEditor() {
        
    }
    
    void addText(string text) {
        left += text;
    }
    
    int deleteText(int k) {
        int deleted = min(k, (int)left.size());
        left.resize(left.size() - deleted);
        return deleted;
    }
    
    string cursorLeft(int k) {
        int moves = min(k, (int)left.size());
        for (int i = 0; i < moves; i++) {
            right.push_back(left.back());
            left.pop_back();
        }
        
        int start = max(0, (int)left.size() - 10);
        return left.substr(start);
    }
    
    string cursorRight(int k) {
        int moves = min(k, (int)right.size());
        for (int i = 0; i < moves; i++) {
            left.push_back(right.back());
            right.pop_back();
        }
        
        int start = max(0, (int)left.size() - 10);
        return left.substr(start);
    }
};

class TextEditor:

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

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

    def deleteText(self, k: int) -> int:
        deleted = min(k, len(self.left))
        for _ in range(deleted):
            self.left.pop()
        return deleted

    def cursorLeft(self, k: int) -> str:
        moves = min(k, len(self.left))
        for _ in range(moves):
            self.right.append(self.left.pop())
        
        return ''.join(self.left[max(0, len(self.left) - 10):])

    def cursorRight(self, k: int) -> str:
        moves = min(k, len(self.right))
        for _ in range(moves):
            self.left.append(self.right.pop())
        
        return ''.join(self.left[max(0, len(self.left) - 10):])

public class TextEditor {
    private List<char> left;
    private List<char> right;

    public TextEditor() {
        left = new List<char>();
        right = new List<char>();
    }
    
    public void AddText(string text) {
        left.AddRange(text.ToCharArray());
    }
    
    public int DeleteText(int k) {
        int deleted = Math.Min(k, left.Count);
        left.RemoveRange(left.Count - deleted, deleted);
        return deleted;
    }
    
    public string CursorLeft(int k) {
        int moves = Math.Min(k, left.Count);
        for (int i = 0; i < moves; i++) {
            right.Add(left[left.Count - 1]);
            left.RemoveAt(left.Count - 1);
        }
        
        int start = Math.Max(0, left.Count - 10);
        return new string(left.GetRange(start, left.Count - start).ToArray());
    }
    
    public string CursorRight(int k) {
        int moves = Math.Min(k, right.Count);
        for (int i = 0; i < moves; i++) {
            left.Add(right[right.Count - 1]);
            right.RemoveAt(right.Count - 1);
        }
        
        int start = Math.Max(0, left.Count - 10);
        return new string(left.GetRange(start, left.Count - start).ToArray());
    }
}

var TextEditor = function() {
    this.left = [];
    this.right = [];
};

TextEditor.prototype.addText = function(text) {
    for (let char of text) {
        this.left.push(char);
    }
};

TextEditor.prototype.deleteText = function(k) {
    let deleted = Math.min(k, this.left.length);
    for (let i = 0; i < deleted; i++) {
        this.left.pop();
    }
    return deleted;
};

TextEditor.prototype.cursorLeft = function(k) {
    let moves = Math.min(k, this.left.length);
    for (let i = 0; i < moves; i++) {
        this.right.push(this.left.pop());
    }
    
    let start = Math.max(0, this.left.length - 10);
    return this.left.slice(start).join('');
};

TextEditor.prototype.cursorRight = function(k) {
    let moves = Math.min(k, this.right.length);
    for (let i = 0; i < moves; i++) {
        this.left.push(this.right.pop());
    }
    
    let start = Math.max(0, this.left.length - 10);
    return this.left.slice(start).join('');
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

操作时间复杂度空间复杂度
addTextO(len(text))O(1)
deleteTextO(k)O(1)
cursorLeftO(k)O(1)
cursorRightO(k)O(1)
总空间复杂度-O(n)

其中 n 是文本的总长度，k 是移动/删除的字符数。所有操作都达到了题目要求的 O(k) 时间复杂度。