题目描述
你的笔记本键盘存在故障,每当你在上面输入字符 'i'
时,它会反转你所写的字符串。而输入其他字符则可以正常工作。
给你一个下标从 0 开始的字符串 s
,请你用故障键盘依次输入每个字符。
返回最终笔记本屏幕上输出的字符串。
样例
输入:s = "string"
输出:"rtsng"
解释:
输入第 1 个字符后,屏幕上的文本是:"s"。
输入第 2 个字符后,屏幕上的文本是:"st"。
输入第 3 个字符后,屏幕上的文本是:"str"。
因为第 4 个字符是 'i',屏幕上的文本被反转,变成 "rts"。
输入第 5 个字符后,屏幕上的文本是:"rtsn" 。
输入第 6 个字符后,屏幕上的文本是:"rtsng"。
因此,返回 "rtsng"。
输入: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'
算法
(模拟) $O(n^2)$
- 直接按照题意模拟,每次遇到
i
反转当前字符串。
时间复杂度
- 每次反转都需要 $O(n)$ 的时间,故时间复杂度为 $O(n)$。
空间复杂度
- 需要 $O(n)$ 的额外空间存储答案。
C++ 代码
class Solution {
public:
string finalString(string s) {
string ans;
for (char c : s) {
if (c == 'i')
reverse(ans.begin(), ans.end());
else
ans += c;
}
return ans;
}
};
算法2
(找规律) $O(n)$
- 每次遇到
i
就反转效率很低,考虑每个以i
分隔的子串,计算其最终是否反转和位置。 - 通过模拟反转过程,可以发现一下规律:
- 一个子串时,答案为 $s_0$;
- 两个子串时,答案为 $s_0’s_1$;
- 三个子串时,答案为 $s_1’s_0s_2$;
- 四个子串时,答案为 $s_2’s_0’s_1s_3$;
- 以此类推,可以得到答案。
时间复杂度
- 每个子串最多反转一次,故时间复杂度为 $O(n)$。
空间复杂度
- 需要 $O(n)$ 的额外空间存储分隔子串的数组和答案。
C++ 代码
class Solution {
public:
string finalString(string s) {
string t;
vector<string> v;
for (int i = 0; i <= s.size(); i++) {
if (i == s.size() || s[i] == 'i') {
v.push_back(t);
t.clear();
} else {
t += s[i];
}
}
string ans;
const int m = v.size();
for (int i = m - 2; i >= 0; i -= 2) {
reverse(v[i].begin(), v[i].end());
ans += v[i];
}
for (int i = 1 - m % 2; i < m; i += 2)
ans += v[i];
return ans;
}
};
算法3
(双端队列) $O(n)$
- 维护一个双端队列,初始从后侧插入字符。
- 遍历字符串,如果遇到
i
,则改为从前方插入字符。 - 如果最终结果是从后侧插入字符,则双端队列就是答案。否则,双端队列的倒序才是答案。
时间复杂度
- 每个字符遍历一次,最多反转一次,故时间复杂度为 $O(n)$。
空间复杂度
- 需要 $O(n)$ 的额外空间存储双端队列和答案。
C++ 代码
class Solution {
public:
string finalString(string s) {
deque<char> v;
bool flag = false;
for (char c : s) {
if (c == 'i') {
flag = !flag;
continue;
}
if (!flag) v.push_back(c);
else v.push_front(c);
}
string ans;
for (char c : v)
ans += c;
if (flag)
reverse(ans.begin(), ans.end());
return ans;
}
};