故障键盘

难度: Easy

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

Submission

运行时间: 24 ms

内存: 15.9 MB

class Solution:
    def finalString(self, s: str) -> str:
        result = []
        for char in s:
            if char == 'i':
                result.reverse()
            else:
                result.append(char)
        return ''.join(result)

Explain

这个题解使用了一个列表来模拟故障键盘的输入过程。对于每一个字符，如果字符是 'i'，则将当前列表中的字符序列反转；如果不是 'i'，则将字符添加到列表的末尾。最后，将列表中的字符拼接成一个字符串作为输出。

时间复杂度: O(n^2)

空间复杂度: O(n)

class Solution:
    def finalString(self, s: str) -> str:
        result = []  # 初始化结果列表
        for char in s:  # 遍历输入字符串的每个字符
            if char == 'i':
                result.reverse()  # 如果当前字符是 'i'，反转结果列表
            else:
                result.append(char)  # 如果不是 'i'，将字符添加到结果列表
        return ''.join(result)  # 将结果列表中的字符合并成字符串并返回

Explore

在Python中，字符串是不可变的数据类型，意味着每次对字符串进行修改都会创建一个新的字符串对象。这样的操作包括添加或删除字符，都会导致额外的内存分配和性能损失。相比之下，列表是可变的，可以在原地进行添加、删除和其他修改操作，特别是在需要多次修改数据时，使用列表会更有效率。因此，为了提高处理效率和减少内存消耗，选择使用列表来存储和修改字符是更合适的选择。

当输入字符串全部由 'i' 组成时，算法将在每次遇到 'i' 时执行反转操作。如果字符串长度为 n，那么将执行 n 次反转操作。由于列表的反转操作时间复杂度为 O(n)，因此整个操作的最坏情况时间复杂度将是 O(n^2)，其中 n 是字符串的长度。这意味着当输入字符串非常长且全由 'i' 组成时，这种方法的性能会显著下降，处理时间会随着输入长度的增加而迅速增加。