Taro Logo

Design a Text Editor

Hard
Amazon logo
Amazon
5 views
Topics:
StringsStacks

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

  1. Add text to where the cursor is.
  2. Delete text from where the cursor is (simulating the backspace key).
  3. 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:

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.

Solution


Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

  1. What specific text editing operations should I prioritize implementing (e.g., insertion, deletion, cursor movement, copy/paste, undo/redo)?
  2. What is the maximum size of the text the editor needs to handle, both in terms of character count and number of lines?
  3. How should the editor handle different character encodings (e.g., ASCII, UTF-8)? Should I assume a specific encoding?
  4. What data structure should I use to represent the text, and are there any constraints on memory usage?
  5. Are there any specific performance requirements for the text editing operations, such as maximum latency for insertion or deletion?

Brute Force Solution

Approach

The brute force approach to designing a text editor means implementing every single editor function directly without considering efficiency. We handle each user action - typing, deleting, moving the cursor - in the most straightforward way possible. This ensures functionality first, optimization later.

Here's how the algorithm would work step-by-step:

  1. When the user types a character, simply add it to the current text displayed.
  2. If the user presses 'delete', remove the character immediately before the cursor.
  3. To move the cursor left, shift its position one character to the left, if possible.
  4. To move the cursor right, shift its position one character to the right, if possible.
  5. When the user enters a newline character, insert a line break at the cursor's position.
  6. For saving, write the entire current text content directly to a file each time the 'save' action is triggered. Overwrite the file completely.
  7. For loading, read the entire content of the file into the text editor's displayed area at once.

Code Implementation

class TextEditor:
    def __init__(self):
        self.text_content = ""
        self.cursor_position = 0

    def type_character(self, character: str):
        """Insert a character at the current cursor position."""
        self.text_content = (
            self.text_content[:self.cursor_position]
            + character
            + self.text_content[self.cursor_position:]
        )
        self.cursor_position += 1

    def delete_character(self):
        """Delete the character before the cursor."""
        if self.cursor_position > 0:
            self.text_content = (
                self.text_content[: self.cursor_position - 1]
                + self.text_content[self.cursor_position :]
            )
            self.cursor_position -= 1

    def move_cursor_left(self):
        """Move cursor one position to the left if possible."""
        if self.cursor_position > 0:
            self.cursor_position -= 1

    def move_cursor_right(self):
        """Move cursor one position to the right if possible."""
        if self.cursor_position < len(self.text_content):
            self.cursor_position += 1

    def insert_newline(self):
        """Insert a newline at the cursor position."""
        self.text_content = (
            self.text_content[:self.cursor_position]
            + "\n"
            + self.text_content[self.cursor_position :]
        )
        self.cursor_position += 1

    def save_file(self, file_path: str):
        """Save the current text to a file."""
        with open(file_path, "w") as file:
            file.write(self.text_content)

    def load_file(self, file_path: str):
        """Load text from a file into the editor."""
        try:
            with open(file_path, "r") as file:
                self.text_content = file.read()
                self.cursor_position = len(self.text_content)
        except FileNotFoundError:
            self.text_content = ""
            self.cursor_position = 0

    def get_text(self) -> str:
        return self.text_content

    def get_cursor_position(self) -> int:
        return self.cursor_position

Big(O) Analysis

Time Complexity
O(n)Let n be the total number of characters in the text editor. Typing a character has O(1) time complexity because we append to the current text. Deleting a character also has O(1) since we are just removing a single character. Moving the cursor left or right takes O(1) time as it's a simple position adjustment. Saving involves writing all n characters to the file, so it is O(n). Loading involves reading all n characters from the file, resulting in O(n). Thus, the overall time complexity is dominated by the save and load operations, leading to O(n).
Space Complexity
O(N)The primary auxiliary space usage comes from storing the current text displayed in the text editor. When the user types, characters are added to this text. The size of this text can grow linearly with the number of characters entered by the user. Saving overwrites the file, but the editor still needs to hold the entire text content in memory; similarly, loading reads the entire file content into the editor's text area. Therefore, the auxiliary space is proportional to N, where N is the number of characters in the current text displayed.

Optimal Solution

Approach

We will simulate a text editor's core functionality. The strategy focuses on maintaining a data structure that efficiently represents the text and allows quick insertion, deletion, and movement of the cursor.

Here's how the algorithm would work step-by-step:

  1. Choose a primary data structure. A linked list, where each element represents a character, is well-suited for this task due to its efficient insertion and deletion capabilities.
  2. Implement the 'insert' operation. When a character is inserted, create a new node in the linked list and link it at the cursor's current position.
  3. Implement the 'delete' operation. When backspace or delete is triggered, remove the appropriate node from the linked list and adjust the links.
  4. Implement cursor movement. Update the cursor's position based on arrow key presses, ensuring it stays within the bounds of the text.
  5. For efficiency, keep track of the current line or paragraph in an organized fashion. Avoid having to traverse the entire text body when determining screen placement.

Code Implementation

class Node:
    def __init__(self, character):
        self.character = character
        self.next = None
        self.previous = None

class TextEditor:
    def __init__(self):
        self.head = Node(None)
        self.tail = Node(None)
        self.head.next = self.tail
        self.tail.previous = self.head
        self.cursor = self.tail

    def insert_character(self, character):
        new_node = Node(character)
        new_node.next = self.cursor
        new_node.previous = self.cursor.previous
        self.cursor.previous.next = new_node
        self.cursor.previous = new_node

    def delete_character(self):
        # Handle cases where there are no characters to delete
        if self.cursor.previous == self.head:
            return

        node_to_delete = self.cursor.previous
        node_to_delete.previous.next = self.cursor
        self.cursor.previous = node_to_delete.previous

    def move_cursor_left(self):
        # Prevent moving beyond the beginning of the text.
        if self.cursor.previous != self.head:
            self.cursor = self.cursor.previous

    def move_cursor_right(self):
        # Keep cursor from going past the end.
        if self.cursor != self.tail:
            self.cursor = self.cursor.next

    def get_text(self):
        text = ""
        current = self.head.next
        while current != self.tail:
            text += current.character
            current = current.next
        return text

Big(O) Analysis

Time Complexity
O(1)The primary data structure is a linked list. Inserting a character involves creating a new node and updating pointers, which takes constant time. Deleting a character also involves updating pointers, a constant-time operation. Cursor movement simply involves updating the cursor's pointer, also a constant-time operation, assuming the cursor position is directly tracked. Therefore, the time complexity of insert, delete, and cursor movement operations is O(1).
Space Complexity
O(N)The primary data structure is a linked list where each node represents a character of the text. In the worst-case scenario, the text editor contains N characters where N is the total number of characters. Therefore, the auxiliary space used by the linked list to store the text is directly proportional to the input size N. The space required to store each node (representing a character) grows linearly with the number of characters, giving us a space complexity of O(N).

Edge Cases

CaseHow to Handle
Empty text bufferInitialize the buffer as an empty string or list; most operations should gracefully handle an empty buffer.
Null input for initial textTreat a null input as an empty string to avoid null pointer exceptions.
Very large text file (exceeding available memory)Implement a streaming or chunking approach to process the text in manageable pieces.
Inserting text at the beginning of the bufferEnsure the insertion logic correctly handles index 0 without off-by-one errors.
Inserting text at the end of the bufferEnsure the insertion logic correctly handles appending to the end of the current text.
Deleting a large chunk of text (close to the entire buffer)Optimize deletion to avoid performance bottlenecks with large removals by using a more efficient string manipulation method.
Handling special characters (Unicode, control characters)Use a Unicode-aware string representation and properly handle control characters to avoid unexpected behavior.
Undo/Redo stack overflow due to excessive operationsImplement a fixed-size undo/redo stack or a more sophisticated memory management strategy to prevent overflow.