How can I efficiently design a text editor with cursor manipulation?

Use a doubly-linked list to represent the text and manage the cursor with pointers. This allows for efficient text modifications and cursor movements.

What are the main challenges in the 'Design a Text Editor' problem?

The main challenges include efficiently managing cursor movements, handling text deletions and additions, and ensuring constant-time operations on the linked list.

How does linked-list pointer manipulation apply in this text editor problem?

Linked-list pointer manipulation allows efficient insertion, deletion, and movement of text characters by directly adjusting node pointers, rather than shifting text in an array.

What operations should the TextEditor class support?

The TextEditor class should support operations like adding text, deleting text, and moving the cursor left or right within the text.

How does GhostInterview help with 'Design a Text Editor' problem-solving?

GhostInterview offers tailored explanations and interactive problem-solving approaches, helping you visualize and implement the text editor with optimal data structures.

#2296

Hard

auto_awesome链表指针操作

LeetCode 题解工作台

设计一个文本编辑器

请你设计一个带光标的文本编辑器，它可以实现以下功能：添加：在光标所在处添加文本。删除：在光标所在处删除文本（模拟键盘的删除键）。移动：将光标往左或者往右移动。当删除文本时，只有光标左边的字符会被删除。光标会留在文本内，也就是说任意时候 0 都成立。请你实现 TextEditor 类：…

链表字符串栈设计模拟

题目描述

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

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

当删除文本时，只有光标左边的字符会被删除。光标会留在文本内，也就是说任意时候 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) 的解决方案吗？

lightbulb

解题思路

方法一：左右栈

我们可以使用两个栈 $\textit{left}$ 和 $\textit{right}$ ，其中栈 $\textit{left}$ 存储光标左边的字符，另一个栈 $\textit{right}$ 存储光标右边的字符。

当调用 $\text{addText}$ 方法时，我们将 $\text{text}$ 中的字符依次入栈 $\text{left}$ 。时间复杂度 $O(|\text{text}|)$ 。
当调用 $\text{deleteText}$ 方法时，我们将 $\text{left}$ 中的字符出栈最多 $k$ 次。时间复杂度 $O(k)$ 。
当调用 $\text{cursorLeft}$ 方法时，我们将 $\text{left}$ 中的字符出栈最多 $k$ 次，然后将出栈的字符依次入栈 $\text{right}$ ，最后返回 $\text{left}$ 栈最多 $10$ 个字符。时间复杂度 $O(k)$ 。
当调用 $\text{cursorRight}$ 方法时，我们将 $\text{right}$ 中的字符出栈最多 $k$ 次，然后将出栈的字符依次入栈 $\text{left}$ ，最后返回 $\text{left}$ 栈最多 $10$ 个字符。时间复杂度 $O(k)$ 。

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

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:
        k = min(k, len(self.left))
        for _ in range(k):
            self.left.pop()
        return k

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

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


# 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)

speed

复杂度分析

指标	值
时间	complexity depends on the operations and the final approach. In the worst case, adding or deleting text could involve traversing a portion of the list, making it O(n) for each operation. However, if the approach is optimized with direct node manipulation, many operations can be O(1). Space complexity is O(n) due to the storage required for the linked list nodes.
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Focus on managing text and cursor efficiently with minimal overhead.
question_mark
Test edge cases where the cursor is near the start or end of the text.
question_mark
Evaluate the candidate’s ability to balance between time complexity and space usage in this linked-list-based approach.

warning

常见陷阱

外企场景

error
Not handling edge cases where the cursor is at the beginning or end of the text.
error
Inefficiently traversing the list during cursor movements or text modifications.
error
Not maintaining the cursor’s position correctly when operations are interleaved.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Design a similar text editor but with undo/redo functionality.
arrow_right_alt
Modify the design to support searching for a substring or replacing text.
arrow_right_alt
Extend the design to support multi-cursor behavior and simultaneous edits.

help

常见问题

外企场景

继续练习

#1472 设计浏览器历史记录 #2211 统计道路上的碰撞次数 #2390 从字符串中移除星号