方法1：双向链表来存储文本，迭代器指向光标所在的位置。加一个dummy head会使代码简单很多。
时间复杂度：TextEditor O(1) addText O(|text|) deleteText O(k) cursorLeft O(k) cursorRight(k)
空间复杂度：O(n)
由于每个字符需要创建一个节点（17+个字节），虽然没有超时，但实际工程中是不能使用这种方式的。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 |
// https://zxi.mytechroad.com/blog/string/leetcode-2296-design-a-text-editor/ class TextEditor { public: TextEditor(): data_{'$'}, cursor_{begin(data_)} {} void addText(string text) { for (char c : text) cursor_ = data_.insert(++cursor_, c); } int deleteText(int k) { for (int i = 0; i < k; ++i) { if (cursor_ == begin(data_)) return i; data_.erase(cursor_--); } return k; } string cursorLeft(int k) { for (int i = 0; i < k; ++i) { if (cursor_ == begin(data_)) break; cursor_--; } return getText(); } string cursorRight(int k) { for (int i = 0; i < k; ++i) { if (cursor_ == prev(end(data_))) break; cursor_++; } return getText(); } private: string getText() { string ans; auto it = cursor_; for (int i = 0; i < 10; ++i) { if (it == begin(data_)) break; ans += *it--; } reverse(begin(ans), end(ans)); return ans; } list<char> data_; list<char>::iterator cursor_; }; |
方法2: 用两个string来代表光标左边的字符串和光标右边的字符串。注：右边字符串是反转的。
左右两边的字符串只会增长（或者覆盖），不会缩短，这是用空间换时间。
删除的时候就是修改了长度而已，并没有缩短字符串，所以是O(1)的。
如果缩短的话需则要O(k)时间，还要加上内存释放/再分配的时间，应该会慢一些但不多。
移动光标的时候，就是把左边字符串的最后k个copy到右边的最后面，或者反过来。同样没有缩短，只会变长。
时间复杂度: TextEditor O(1) addText O(|text|) deleteText O(1) cursorLeft O(k) cursorRight(k)
空间复杂度：O(n)，n为构建的最长的字符串
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 |
// https://zxi.mytechroad.com/blog/string/leetcode-2296-design-a-text-editor/ class TextEditor { public: TextEditor() {} void addText(string_view text) { ensureSize(l, m + text.size()); copy(begin(text), end(text), begin(l) + m); m += text.size(); } int deleteText(int k) { k = min(k, m); m -= k; return k; } string cursorLeft(int k) { ensureSize(r, n + k); for (k = min(k, m); k > 0; --k) r[n++] = l[--m]; return getText(); } string cursorRight(int k) { ensureSize(l, m + k); for (k = min(k, n); k > 0; --k) l[m++] = r[--n]; return getText(); } private: inline void ensureSize(string& s, int size) { if (s.size() < size) s.resize(size); } string getText() const { return string(begin(l) + m - min(m, 10), begin(l) + m); } string l; string r; int m = 0; int n = 0; }; |