How do you solve Design a Text Editor on LeetCode?

Design a Text Editor (LeetCode #2296) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(n) time complexity and O(n) space complexity. Key insight: Using a doubly linked list allows for efficient insertions and deletions, especially when managing a cursor.

What is the brute force solution for Design a Text Editor?

The brute force approach for Design a Text Editor is Brute Force, with O(n²) time complexity and O(1) space complexity. The brute force approach involves using a simple string to represent the text and manipulating it directly for each operation. While this is straightforward, it can be inefficient for operations that require frequent insertions and deletions. The optimal Optimal Solution approach improves this to O(n).

What algorithm or data structure is used to solve Design a Text Editor?

Design a Text Editor uses the following concepts: Linked List, String, Stack, Design, Simulation, Doubly-Linked List. The recommended patterns to study are: Doubly Linked List, Simulation.

What are the interview tips for Design a Text Editor?

Think about how to efficiently manage state changes, especially with a cursor. Practice implementing data structures like linked lists, as they often come up in design problems. Always consider edge cases and test your implementation with various inputs.

What are common mistakes when solving Design a Text Editor?

Failing to manage the cursor correctly, leading to out-of-bounds errors. Not considering edge cases, such as deleting more characters than available.

#2296

Design a Text Editor

Hard

Linked ListStringStackDesignSimulationDoubly-Linked ListDoubly Linked ListSimulation

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(n²)	O(n)
Space	O(1)	O(n)

💡

Intuition

Time O(n)Space O(n)

The optimal approach uses a doubly linked list to represent the text, allowing efficient insertions and deletions at both ends. This structure allows us to manage the text and cursor position without needing to manipulate a large string frequently.

⚙️

Algorithm

5 steps

1Step 1: Use a doubly linked list where each node represents a character.
2Step 2: Maintain two pointers: one for the current node (cursor) and one for the head of the list.
3Step 3: For 'addText', create new nodes and link them at the cursor position.
4Step 4: For 'deleteText', traverse left from the cursor and remove nodes as needed.
5Step 5: For 'cursorLeft' and 'cursorRight', move the cursor pointer accordingly.

solution.py49 lines

1class Node:
2    def __init__(self, char):
3        self.char = char
4        self.prev = None
5        self.next = None
6
7class TextEditor:
8    def __init__(self):
9        self.head = None
10        self.cursor = None
11
12    def addText(self, text: str) -> None:
13        for char in text:
14            new_node = Node(char)
15            if not self.head:
16                self.head = new_node
17                self.cursor = new_node
18            else:
19                new_node.prev = self.cursor
20                self.cursor.next = new_node
21                self.cursor = new_node
22
23    def deleteText(self, k: int) -> int:
24        delete_count = 0
25        while self.cursor and delete_count < k:
26            self.cursor = self.cursor.prev
27            delete_count += 1
28        return delete_count
29
30    def cursorLeft(self, k: int) -> str:
31        for _ in range(k):
32            if self.cursor:
33                self.cursor = self.cursor.prev
34        return self.getLeftChars()
35
36    def cursorRight(self, k: int) -> str:
37        for _ in range(k):
38            if self.cursor and self.cursor.next:
39                self.cursor = self.cursor.next
40        return self.getLeftChars()
41
42    def getLeftChars(self):
43        chars = []
44        current = self.cursor
45        for _ in range(10):
46            if current:
47                chars.append(current.char)
48                current = current.prev
49        return ''.join(reversed(chars))

ℹ

Complexity note: The time complexity is O(n) for adding or deleting text because we traverse the linked list to create or remove nodes, but each operation is efficient due to the linked structure.

1Using a doubly linked list allows for efficient insertions and deletions, especially when managing a cursor.
2Maintaining a cursor pointer helps in tracking the current position without needing to slice strings.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.