{x}
blog image

Design a Text Editor

Design a text editor with a cursor that can do the following:

  • Add text to where the cursor is.
  • Delete text from where the cursor is (simulating the backspace key).
  • Move the cursor either left or right.

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 <= 40
  • text consists of lowercase English letters.
  • At most 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?

Solution: Design a Text Editor using Stacks

This problem can be efficiently solved using two stacks: left and right. left stores characters to the left of the cursor, and right stores characters to the right. This allows for $O(k)$ time complexity for most operations.

Data Structures:

  • left: A stack (list in Python, StringBuilder in Java, etc.) storing characters to the left of the cursor.
  • right: A stack (list in Python, StringBuilder in Java, etc.) storing characters to the right of the cursor.

Methods:

  • addText(text: str): Appends text to the left stack. Time complexity: O(len(text))

  • deleteText(k: int): Removes k characters from the end of the left stack. Time complexity: O(min(k, len(left)))

  • cursorLeft(k: int): Moves the cursor left k positions. It pops k characters from left and pushes them onto right. It then returns the last 10 characters from left. Time complexity: O(min(k, len(left)))

  • cursorRight(k: int): Moves the cursor right k positions. It pops k characters from right and pushes them onto left. It then returns the last 10 characters from left. Time complexity: O(min(k, len(right)))

Time Complexity Analysis:

  • addText: O(len(text)) - Linear in the length of the added text.
  • deleteText: O(min(k, len(left))) - Linear in the number of characters deleted, up to the length of the left stack.
  • cursorLeft: O(min(k, len(left))) - Linear in the number of cursor movements left, up to the length of the left stack.
  • cursorRight: O(min(k, len(right))) - Linear in the number of cursor movements right, up to the length of the right stack.

Space Complexity: O(n), where n is the total number of characters in the text editor at any given time. This is because we store all the characters in the two stacks.

Code Examples:

The code examples in Python, Java, C++, Go, and TypeScript are provided in the original response. They all implement the above logic using their respective language's stack-like structures. Each function's time complexity aligns with the analysis above. The code efficiently handles edge cases like moving the cursor beyond the text boundaries or attempting to delete more characters than exist.