2296. 设计一个文本编辑器
请你设计一个带光标的文本编辑器，它可以实现以下功能：
当删除文本时，只有光标左边的字符会被删除。光标会留在文本内，也就是说任意时候 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 <= 40text 只含有小写英文字母。addText ，deleteText ，cursorLeft 和 cursorRight 的 总 次数不超过 2 * 104 次。
进阶：你能设计并实现一个每次调用时间复杂度为 O(k) 的解决方案吗？
原站题解
java 解法, 执行用时: 139 ms, 内存消耗: 103.8 MB, 提交时间: 2023-09-07 11:04:10
class TextEditor {
Node root, cur;
public TextEditor() {
root = cur = new Node(); // 哨兵节点
root.prev = root;
root.next = root; // 初始化双向链表，下面判断节点的 next 若为 root，则表示 next 为空
}
public void addText(String text) {
for (var i = 0; i < text.length(); i++)
cur = cur.insert(new Node(text.charAt(i)));
}
public int deleteText(int k) {
var k0 = k;
for (; k > 0 && cur != root; --k) {
cur = cur.prev;
cur.next.remove();
}
return k0 - k;
}
String text() {
var s = new StringBuilder();
var cur = this.cur;
for (var k = 10; k > 0 && cur != root; --k) {
s.append(cur.ch);
cur = cur.prev;
}
return s.reverse().toString();
}
public String cursorLeft(int k) {
for (; k > 0 && cur != root; --k)
cur = cur.prev;
return text();
}
public String cursorRight(int k) {
for (; k > 0 && cur.next != root; --k)
cur = cur.next;
return text();
}
}
// 手写双向链表
class Node {
Node prev, next;
char ch;
Node() {}
Node(char ch) {
this.ch = ch;
}
// 在 this 后插入 node，并返回该 node
Node insert(Node node) {
node.prev = this;
node.next = this.next;
node.prev.next = node;
node.next.prev = node;
return node;
}
// 从链表中移除 this
void remove() {
this.prev.next = this.next;
this.next.prev = this.prev;
}
}
/**
* Your TextEditor object will be instantiated and called as such:
* TextEditor obj = new TextEditor();
* obj.addText(text);
* int param_2 = obj.deleteText(k);
* String param_3 = obj.cursorLeft(k);
* String param_4 = obj.cursorRight(k);
*/
golang 解法, 执行用时: 208 ms, 内存消耗: 14.6 MB, 提交时间: 2023-09-07 11:03:11
type TextEditor struct{ l, r []byte }
func Constructor() TextEditor { return TextEditor{} }
func (t *TextEditor) AddText(text string) {
t.l = append(t.l, text...)
}
func (t *TextEditor) DeleteText(k int) int {
if k < len(t.l) {
t.l = t.l[:len(t.l)-k]
} else {
k = len(t.l)
t.l = t.l[:0]
}
return k
}
func (t *TextEditor) text() string {
return string(t.l[max(len(t.l)-10, 0):])
}
func (t *TextEditor) CursorLeft(k int) string {
for ; k > 0 && len(t.l) > 0; k-- {
t.r = append(t.r, t.l[len(t.l)-1])
t.l = t.l[:len(t.l)-1]
}
return t.text()
}
func (t *TextEditor) CursorRight(k int) string {
for ; k > 0 && len(t.r) > 0; k-- {
t.l = append(t.l, t.r[len(t.r)-1])
t.r = t.r[:len(t.r)-1]
}
return t.text()
}
func max(a, b int) int { if b > a { return b }; return a }
/**
* Your TextEditor object will be instantiated and called as such:
* obj := Constructor();
* obj.AddText(text);
* param_2 := obj.DeleteText(k);
* param_3 := obj.CursorLeft(k);
* param_4 := obj.CursorRight(k);
*/
golang 解法, 执行用时: 668 ms, 内存消耗: 105.1 MB, 提交时间: 2023-09-07 11:02:47
type TextEditor struct {
*list.List
cur *list.Element
}
func Constructor() TextEditor {
l := list.New()
return TextEditor{l, l.PushBack(nil)} // 哨兵节点
}
func (l *TextEditor) AddText(text string) {
for _, ch := range text {
l.cur = l.InsertAfter(byte(ch), l.cur)
}
}
func (l *TextEditor) DeleteText(k int) int {
k0 := k
for ; k > 0 && l.cur.Value != nil; k-- {
pre := l.cur.Prev()
l.Remove(l.cur)
l.cur = pre
}
return k0 - k
}
func (l *TextEditor) text() string {
s := []byte{}
for k, cur := 10, l.cur; k > 0 && cur.Value != nil; k-- {
s = append(s, cur.Value.(byte))
cur = cur.Prev()
}
for i, n := 0, len(s); i < n/2; i++ {
s[i], s[n-1-i] = s[n-1-i], s[i] // reverse s
}
return string(s)
}
func (l *TextEditor) CursorLeft(k int) string {
for ; k > 0 && l.cur.Value != nil; k-- {
l.cur = l.cur.Prev()
}
return l.text()
}
func (l *TextEditor) CursorRight(k int) string {
for ; k > 0 && l.cur.Next() != nil; k-- {
l.cur = l.cur.Next()
}
return l.text()
}
/**
* Your TextEditor object will be instantiated and called as such:
* obj := Constructor();
* obj.AddText(text);
* param_2 := obj.DeleteText(k);
* param_3 := obj.CursorLeft(k);
* param_4 := obj.CursorRight(k);
*/
python3 解法, 执行用时: 348 ms, 内存消耗: 35.5 MB, 提交时间: 2023-09-07 11:02:21
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:
k0 = k
while k and self.left:
self.left.pop()
k -= 1
return k0 - k
def text(self) -> str:
return ''.join(self.left[-10:])
def cursorLeft(self, k: int) -> str:
while k and self.left:
self.right.append(self.left.pop())
k -= 1
return self.text()
def cursorRight(self, k: int) -> str:
while k and self.right:
self.left.append(self.right.pop())
k -= 1
return self.text()
# 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)
python3 解法, 执行用时: 3192 ms, 内存消耗: 77.7 MB, 提交时间: 2023-09-07 11:02:03
# 手写双向链表
class Node:
__slots__ = 'prev', 'next', 'ch'
def __init__(self, ch=''):
self.prev = None
self.next = None
self.ch = ch
# 在 self 后插入 node，并返回该 node
def insert(self, node: 'Node') -> 'Node':
node.prev = self
node.next = self.next
node.prev.next = node
node.next.prev = node
return node
# 从链表中移除 self
def remove(self) -> None:
self.prev.next = self.next
self.next.prev = self.prev
class TextEditor:
def __init__(self):
self.root = self.cur = Node() # 哨兵节点
self.root.prev = self.root
self.root.next = self.root # 初始化双向链表，下面判断节点的 next 若为 self.root，则表示 next 为空
def addText(self, text: str) -> None:
for ch in text:
self.cur = self.cur.insert(Node(ch))
def deleteText(self, k: int) -> int:
k0 = k
while k and self.cur != self.root:
self.cur = self.cur.prev
self.cur.next.remove()
k -= 1
return k0 - k
def text(self) -> str:
s = []
k, cur = 10, self.cur
while k and cur != self.root:
s.append(cur.ch)
cur = cur.prev
k -= 1
return ''.join(reversed(s))
def cursorLeft(self, k: int) -> str:
while k and self.cur != self.root:
self.cur = self.cur.prev
k -= 1
return self.text()
def cursorRight(self, k: int) -> str:
while k and self.cur.next != self.root:
self.cur = self.cur.next
k -= 1
return self.text()
# 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)