题目
你的笔记本键盘存在故障，每当你在上面输入字符
′
i
′
'i'
′i′ 时，它会反转你所写的字符串。而输入其他字符则可以正常工作。
给你一个下标从
0
0
0 开始的字符串
s
s
s ，请你用故障键盘依次输入每个字符。
返回最终笔记本屏幕上输出的字符串。
示例 2：
输入：s = “poiinter”
输出：“ponter”
解释：
输入第
1
1
1 个字符后，屏幕上的文本是：
"
p
"
"p"
"p" 。
输入第
2
2
2 个字符后，屏幕上的文本是：
"
p
o
"
"po"
"po" 。
因为第
3
3
3 个字符是
′
i
′
'i'
′i′ ，屏幕上的文本被反转，变成
"
o
p
"
"op"
"op" 。
因为第
4
4
4 个字符是
′
i
′
'i'
′i′ ，屏幕上的文本被反转，变成
"
p
o
"
"po"
"po" 。
输入第
5
5
5 个字符后，屏幕上的文本是：
"
p
o
n
"
"pon"
"pon" 。
输入第
6
6
6 个字符后，屏幕上的文本是：
"
p
o
n
t
"
"pont"
"pont" 。
输入第
7
7
7 个字符后，屏幕上的文本是：
"
p
o
n
t
e
"
"ponte"
"ponte" 。
输入第
8
8
8 个字符后，屏幕上的文本是：
"
p
o
n
t
e
r
"
"ponter"
"ponter" 。
因此，返回
"
p
o
n
t
e
r
"
"ponter"
"ponter" 。
提示：
-
1
≤
s
.
l
e
n
g
t
h
≤
100
1 \leq s.length \leq 100
1≤s.length≤100
-
s
s
s 由小写英文字母组成
-
s
[
0
]
!
=
′
i
′
s[0] != 'i'
s[0]!=′i′
思路
这道题目要求模拟故障键盘的输入，其中故障键盘会在输入字符 ‘i’ 时反转已输入的字符串，而其他字符则正常输入。所以我们需要一个变量来追踪当前输入的方向（从左到右或从右到左），以及一个数据结构来存储已输入的字符。
- 如果是字符
′
i
′
'i'
′i′，则将
l
e
f
t
2
r
i
g
h
t
left2right
left2right 取反，表示要改变输入方向。
- 如果当前输入方向是从左到右，则将字符加入到双端队列的末尾。
- 如果当前输入方向是从右到左，则将字符加入到双端队列的开头。
- 根据
l
e
f
t
2
r
i
g
h
t
left2right
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
)
O(n)
O(n)
结果
总结
通过维护输入方向和使用双端队列，可以在
O
(
n
)
O(n)
O(n) 的时间和
O
(
n
)
O(n)
O(n) 的空间内完成
