双端队列，LeetCode 2810. 故障键盘

一、题目

1、题目描述

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

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

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

2、接口描述

​​cpp

class Solution {
public:
    string finalString(string s) {
        
    }
};

  python3

class Solution:
    def finalString(self, s: str) -> str:

3、原题链接

2810. 故障键盘

---

二、解题报告

1、思路分析

反转<=>往字符串的头部添加字符

那么遍历的时候维护方向然后添加字符即可

这要求两端都能添加元素的数据结构所以可以想到双端队列

2、复杂度

时间复杂度：O(n) 空间复杂度：O(n)

3、代码详解

​cpp

class Solution {
public:
    string finalString(string s) {
        deque<char> dq;
        bool rev = 0;
        for(char ch : s){
            if(ch == 'i') rev ^= 1;
            else if(rev) dq.push_front(ch);
            else dq.push_back(ch);
        }
        return rev ? string(dq.rbegin(), dq.rend()) : string(dq.begin(), dq.end());
    }
};

 python3

class Solution:
    def finalString(self, s: str) -> str:
        q = deque()
        rev = True
        for x in s:
            if x == 'i':
                rev = not rev
            elif rev:
                q.append(x)
            else:
                q.appendleft(x)
        return ''.join(q if rev else reversed(q))