2810. 故障键盘

题目描述：

你的笔记本键盘存在故障，每当你在上面输入字符 ‘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 由小写英文字母组成100
• s[0] != ‘i’

---

解题分析及思路：

方法：队列

思路：

该题可以简化：

• 未遇到i时，将字符添加到结果集末尾
• 否则，将结果集反转，并且后续字符添加到结果集末尾

理论上直接模拟就可以进行解答，但是每次反转都需要浪费时间。

那么可以利用队列的特性，可以简化为：

• 未遇到i时，将字符添加到结果集末尾
• 否则，将后续字符添加到结果集开头

那么，只需在最后判断结果集是否需要反转即可。

func finalString(s string) string {
	var result []byte
	var flag = false
	for index := range s {
		if s[index] == 'i' {
			flag = !flag
		} else {
			if flag {
				result = append(result, s[index])
			} else {
				result = append([]byte{s[index]}, result...)
			}
		}
	}
	if !flag {
		for index := 0; index < len(result)/2; index++ {
			result[index], result[len(result)-index-1] = result[len(result)-index-1], result[index]
		}
	}
	return string(result)
}

复杂度：

• 时间复杂度：O(N)
• 空间复杂度：O(N)

执行结果：

• 执行耗时:3 ms,击败了87.50% 的Go用户
• 内存消耗:3.3 MB,击败了35.00% 的Go用户