Design a text editor with a cursor that can do the following:
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.
Example 1:
Input
["TextEditor", "addText", "deleteText", "addText", "cursorRight", "cursorLeft", "deleteText", "cursorLeft", "cursorRight"]
[[], ["leetcode"], [4], ["practice"], [3], [8], [10], [2], [6]]
Output
[null, null, 4, null, "etpractice", "leet", 4, "", "practi"]
Explanation
TextEditor textEditor = new TextEditor(); // The current text is "|". (The '|' character represents the cursor)
textEditor.addText("leetcode"); // The current text is "leetcode|".
textEditor.deleteText(4); // return 4
// The current text is "leet|".
// 4 characters were deleted.
textEditor.addText("practice"); // The current text is "leetpractice|".
textEditor.cursorRight(3); // return "etpractice"
// The current text is "leetpractice|".
// The cursor cannot be moved beyond the actual text and thus did not move.
// "etpractice" is the last 10 characters to the left of the cursor.
textEditor.cursorLeft(8); // return "leet"
// The current text is "leet|practice".
// "leet" is the last min(10, 4) = 4 characters to the left of the cursor.
textEditor.deleteText(10); // return 4
// The current text is "|practice".
// Only 4 characters were deleted.
textEditor.cursorLeft(2); // return ""
// The current text is "|practice".
// The cursor cannot be moved beyond the actual text and thus did not move.
// "" is the last min(10, 0) = 0 characters to the left of the cursor.
textEditor.cursorRight(6); // return "practi"
// The current text is "practi|ce".
// "practi" is the last min(10, 6) = 6 characters to the left of the cursor.
Constraints:
1 <= text.length, k <= 40text consists of lowercase English letters.2 * 104 calls in total will be made to addText, deleteText, cursorLeft and cursorRight.
Follow-up: Could you find a solution with time complexity of O(k) per call?
Problem Overview: You need to design a text editor that supports operations such as inserting text, deleting characters to the left of the cursor, and moving the cursor left or right. After cursor movement, the editor must return up to the last 10 characters to the left of the cursor. The challenge is maintaining efficient updates while simulating real editor behavior.
Approach 1: Split List Data Structure (Two Stacks Simulation) (Time: O(k) per operation, Space: O(n))
Maintain two dynamic lists representing text on the left and right of the cursor. The left list stores characters before the cursor, and the right list stores characters after it. Adding text pushes characters onto the left list. Deleting removes characters from the end of the left list. Cursor movement transfers characters between the lists: moving left pops from the left list and pushes to the right list, while moving right does the opposite. This split structure simulates cursor behavior efficiently because each character move is constant time. When returning the last 10 characters, slice the tail of the left list. This approach works well in Python or JavaScript because arrays support fast append and pop operations.
Approach 2: Node-Based Doubly Linked List (Time: O(k) per operation, Space: O(n))
Model the editor using a doubly linked list where each node represents a character. Maintain a pointer to the current cursor position. Inserting text creates new nodes and links them directly before the cursor. Deleting characters walks backward from the cursor and removes nodes while fixing the prev and next references. Cursor movement simply updates the pointer by traversing through neighboring nodes. Retrieving the last 10 characters requires iterating up to 10 nodes to the left of the cursor. This structure closely mirrors how text editors internally represent editable buffers and demonstrates strong understanding of linked list manipulation.
Recommended for interviews: The split list approach is usually preferred. It is simpler to implement, avoids pointer bugs, and clearly demonstrates how a stack-like structure can simulate cursor movement. The doubly linked list version shows deeper knowledge of data structure design and pointer manipulation, which some interviewers appreciate for system-style problems. Showing both ideas demonstrates understanding of simulation tradeoffs and editor buffer design.
We model the text editor as two lists, 'left' and 'right', representing text to the left and right of the cursor respectively. This simulates efficient text editing operations by leveraging lists for append and pop operations. The cursor position is implicitly represented as the boundary between the two lists. Thus, operations like cursor movements and text manipulations can be done efficiently.
The implementation uses two lists, 'left' and 'right'. The 'addText' method appends characters to the 'left' list simulating the cursor being at the end of 'left'. The 'deleteText' method removes characters from the end of the 'left' list. The cursor manipulations use the 'pop' and 'append' methods to move characters between the two lists, maintaining efficient operations.
Python
JavaScript
Time Complexity: O(k) per operation, since at most k characters are processed.
Space Complexity: O(n), where n is the length of the text stored.
This approach involves a custom implementation of a doubly linked list to maintain character sequences. The text is modeled using nodes where each node represents a character. The cursor is a pointer to the current node, enabling dynamic and efficient character operations akin to list insertions and deletions with cursor adjustments.
The Java solution implements a doubly linked list, where nodes are linked bidirectionally. This allows efficient addition, deletion, and cursor movement. The dummy cursor node acts as a guide, and moving left or right is akin to traversing the linked structure. This provides a highly flexible editor model.
Time Complexity: O(k), k being the number of characters moving or deleting.
Space Complexity: O(n), where n is the number of characters in the text.
We can use two stacks, left and right, where the stack left stores the characters to the left of the cursor, and the stack right stores the characters to the right of the cursor.
addText method, we push the characters in text onto the left stack one by one. The time complexity is O(|text|).deleteText method, we pop characters from the left stack up to k times. The time complexity is O(k).cursorLeft method, we pop characters from the left stack up to k times, then push the popped characters onto the right stack one by one, and finally return up to 10 characters from the left stack. The time complexity is O(k).cursorRight method, we pop characters from the right stack up to k times, then push the popped characters onto the left stack one by one, and finally return up to 10 characters from the left stack. The time complexity is O(k).| Approach | Complexity |
|---|---|
| Split List Data Structure | Time Complexity: O(k) per operation, since at most k characters are processed. |
| Nodes Based Doubly Linked List | Time Complexity: O(k), k being the number of characters moving or deleting. |
| Left and Right Stacks | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Split List (Two Stacks) | O(k) per operation | O(n) | Preferred for Python/JavaScript implementations where array push/pop are efficient |
| Node-Based Doubly Linked List | O(k) per operation | O(n) | Useful when practicing pointer manipulation or implementing editor buffers |
2296. Design a Text Editor (Leetcode Hard) • Programming Live with Larry • 2,402 views views
Watch 9 more video solutions →Practice Design a Text Editor with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor