LeetCode 2810.故障键盘

本文主要是介绍LeetCode 2810.故障键盘，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

你的笔记本键盘存在故障，每当你在上面输入字符 ‘i’ 时，它会反转你所写的字符串。而输入其他字符则可以正常工作。

给你一个下标从 0 开始的字符串 s ，请你用故障键盘依次输入每个字符。

返回最终笔记本屏幕上输出的字符串。

示例 1：

输入：s = “string”
输出：“rtsng”
解释：
输入第 1 个字符后，屏幕上的文本是：“s” 。
输入第 2 个字符后，屏幕上的文本是：“st” 。
输入第 3 个字符后，屏幕上的文本是：“str” 。
因为第 4 个字符是 ‘i’ ，屏幕上的文本被反转，变成 “rts” 。
输入第 5 个字符后，屏幕上的文本是：“rtsn” 。
输入第 6 个字符后，屏幕上的文本是： “rtsng” 。
因此，返回 “rtsng” 。
示例 2：

输入：s = “poiinter”
输出：“ponter”
解释：
输入第 1 个字符后，屏幕上的文本是：“p” 。
输入第 2 个字符后，屏幕上的文本是：“po” 。
因为第 3 个字符是 ‘i’ ，屏幕上的文本被反转，变成 “op” 。
因为第 4 个字符是 ‘i’ ，屏幕上的文本被反转，变成 “po” 。
输入第 5 个字符后，屏幕上的文本是：“pon” 。
输入第 6 个字符后，屏幕上的文本是：“pont” 。
输入第 7 个字符后，屏幕上的文本是：“ponte” 。
输入第 8 个字符后，屏幕上的文本是：“ponter” 。
因此，返回 “ponter” 。

提示：

1 <= s.length <= 100
s 由小写英文字母组成
s[0] != ‘i’

法一：遍历一遍s，每遇到i就翻转前面包括i在内的所有字符，因为有没有i都不影响除i以外的字符的相对顺序，最后再删掉i即可：

class Solution {
public:string finalString(string s) {for (int i = 0; i < s.size(); ++i){if (s[i] == 'i'){reverse(s, 0, i);}}size_t pos = string::npos;while ((pos = s.find('i')) != string::npos){s.erase(pos, 1);}return s;}private:void reverse(string &s, int begin, int end){while (begin < end){swap(s[begin++], s[end--]);}}
};

如果s的长度为n，则此算法时间复杂度为O(n $^2$ )，空间复杂度为O(1)。

法二：每次出现i可看作往相反的方向将字符添加到结果字符串，如string，遍历到i前，正向存入结果str，遇到i后，反向存入结果gnstr，如果根据方向翻转结果为rtsng：

class Solution {
public:string finalString(string s) {// 由于要双向存结果，因此选用双向队列deque<char> dq;bool tail = true;for (char c : s){if (c == 'i'){tail = !tail;}else if (tail){dq.push_back(c);}else{dq.push_front(c);}}return tail ? string(dq.begin(), dq.end()) : string(dq.rbegin(), dq.rend());}
};