题目

题目链接🔗
你的笔记本键盘存在故障，每当你在上面输入字符 ${}^{\prime }{i}^{\prime }$ 时，它会反转你所写的字符串。而输入其他字符则可以正常工作。

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

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

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

示例 2：

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

提示：

• $1\le s.length\le 100$
• $s$ 由小写英文字母组成
• $s[0]!{=}^{\prime }{i}^{\prime }$

思路

这道题目要求模拟故障键盘的输入，其中故障键盘会在输入字符 ‘i’ 时反转已输入的字符串，而其他字符则正常输入。所以我们需要一个变量来追踪当前输入的方向（从左到右或从右到左），以及一个数据结构来存储已输入的字符。

1. 使用一个 $deque$（双端队列）来存储字符，因为我们需要在两端进行插入操作。
2. 使用一个布尔变量 $left2right$ 来追踪当前输入方向，初始值为 $true$ 表示从左到右。
3. 遍历字符串 $s$，对于每个字符：

• 如果是字符 ${}^{\prime }{i}^{\prime }$，则将 $left2right$ 取反，表示要改变输入方向。
• 如果当前输入方向是从左到右，则将字符加入到双端队列的末尾。
• 如果当前输入方向是从右到左，则将字符加入到双端队列的开头。

4. 根据 $left2right$ 的值来确定最终输出的字符串是正序还是逆序。

代码

class Solution {
public:
    string finalString(string s) {
        deque<char> dq;
        bool left2right = true;  // 从左到右
        for (int i = 0; i < s.length(); ++i) 
        {
            if (s[i] == 'i') left2right = !left2right;  // 反向
            else if (left2right) dq.push_back(s[i]);
            else dq.push_front(s[i]);
        }
        return left2right ? string(dq.begin(), dq.end()) : string(dq.rbegin(), dq.rend());
    }
};

复杂度分析

时间复杂度

$O(n)$

空间复杂度

$O(n)$

结果

总结

通过维护输入方向和使用双端队列，可以在 $O(n)$ 的时间和 $O(n)$ 的空间内完成