2810-故障键盘

Raphael Liu Lv10
  2023-09-13 00:47:26 2023-09-13 00:47:26 Created   2023-09-13 16:06:27 2023-09-13 16:06:27 Updated    

你的笔记本键盘存在故障，每当你在上面输入字符 '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'

视频讲解

把反转看成是后续往字符串的头部添加字符。

这可以用双端队列实现。

不想用双端队列的话，可以参考下面 Go 语言代码的实现。

[sol-Python3]
1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
    def finalString(self, s: str) -> str:
        q = deque()
        tail = True
        for c in s:
            if c == 'i':
                tail = not tail  # 修改添加方向
            elif tail:  # 加尾部
                q.append(c)
            else:  # 加头部
                q.appendleft(c)
        return ''.join(q if tail else reversed(q))
[sol-Java]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    public String finalString(String s) {
        var q = new ArrayDeque<Character>();
        var tail = true;
        for (var c : s.toCharArray()) {
            if (c == 'i') tail = !tail;
            else if (tail) q.addLast(c);
            else q.addFirst(c);
        }
        var ans = new StringBuilder();
        for (var c : q) ans.append(c);
        if (!tail) ans.reverse();
        return ans.toString();
    }
}
[sol-C++]
1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    string finalString(string s) {
        deque<char> q;
        bool tail = true;
        for (char c: s) {
            if (c == 'i') tail = !tail;
            else if (tail) q.push_back(c);
            else q.push_front(c);
        }
        return tail ? string(q.begin(), q.end()) : string(q.rbegin(), q.rend());
    }
};
[sol-Go]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
func finalString(s string) string {
	qs := [2][]rune{}
	tail := 1
	for _, c := range s {
		if c == 'i' {
			tail ^= 1
		} else {
			qs[tail] = append(qs[tail], c)
		}
	}
	q := qs[tail^1]
	for i, n := 0, len(q); i < n/2; i++ {
		q[i], q[n-1-i] = q[n-1-i], q[i]
	}
	return string(append(q, qs[tail]...))
}

复杂度分析

  • 时间复杂度：\mathcal{O}(n)，其中 n 为 s 的长度。
  • 空间复杂度：\mathcal{O}(n)。
 Comments
On this page
2810-故障键盘