Easy

题目描述

你的笔记本电脑键盘坏了，每当你在上面输入字符 ‘i’ 时，它会反转你已经写的字符串。输入其他字符按预期工作。

给你一个 0 索引的字符串 s，你使用故障键盘输入 s 的每个字符。

返回最终会出现在你笔记本电脑屏幕上的字符串。

示例 1：

输入：s = "string"
输出："rtsng"
解释：
输入第一个字符后，屏幕上的文本是 "s"。
输入第二个字符后，文本是 "st"。
输入第三个字符后，文本是 "str"。
由于第四个字符是 'i'，文本被反转变成 "rts"。
输入第五个字符后，文本是 "rtsn"。
输入第六个字符后，文本是 "rtsng"。
因此，我们返回 "rtsng"。

示例 2：

输入：s = "poiinter"
输出："ponter"
解释：
输入第一个字符后，屏幕上的文本是 "p"。
输入第二个字符后，文本是 "po"。
由于你输入的第三个字符是 'i'，文本被反转变成 "op"。
由于你输入的第四个字符是 'i'，文本被反转变成 "po"。
输入第五个字符后，文本是 "pon"。
输入第六个字符后，文本是 "pont"。
输入第七个字符后，文本是 "ponte"。
输入第八个字符后，文本是 "ponter"。
因此，我们返回 "ponter"。

约束条件：

  • 1 <= s.length <= 100
  • s 由小写英文字母组成
  • s[0] != ‘i’

解题思路

这道题是一个典型的模拟问题。我们需要按照题目描述的规则逐个处理字符串中的每个字符。

解题思路：

  1. 直接模拟法：遍历输入字符串，维护一个结果字符串。当遇到非 ‘i’ 字符时，将其添加到结果字符串末尾；当遇到 ‘i’ 字符时，将当前结果字符串反转。

  2. 优化思考：由于字符串长度最大只有100，直接模拟的时间复杂度完全可以接受。每次反转操作的复杂度是O(n)，最坏情况下需要反转多次，但由于数据规模较小，不需要过度优化。

  3. 实现要点：

    • 初始化一个空的结果字符串
    • 遍历输入字符串的每个字符
    • 如果字符不是 ‘i’，直接添加到结果字符串
    • 如果字符是 ‘i’，对当前结果字符串进行反转
    • 返回最终的结果字符串

这种方法简单直观，代码易于理解和实现，时间复杂度为O(n²)（最坏情况下每个字符都是’i’），空间复杂度为O(n)。

代码实现

class Solution {
public:
    string finalString(string s) {
        string result = "";
        for (char c : s) {
            if (c == 'i') {
                reverse(result.begin(), result.end());
            } else {
                result += c;
            }
        }
        return result;
    }
};

class Solution:
    def finalString(self, s: str) -> str:
        result = ""
        for c in s:
            if c == 'i':
                result = result[::-1]
            else:
                result += c
        return result

public class Solution {
    public string FinalString(string s) {
        string result = "";
        foreach (char c in s) {
            if (c == 'i') {
                char[] arr = result.ToCharArray();
                Array.Reverse(arr);
                result = new string(arr);
            } else {
                result += c;
            }
        }
        return result;
    }
}

var finalString = function(s) {
    let result = "";
    
    for (let char of s) {
        if (char === 'i') {
            result = result.split('').reverse().join('');
        } else {
            result += char;
        }
    }
    
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n²)最坏情况下每个字符都是’i’，需要进行n次反转，每次反转O(n)
空间复杂度O(n)需要存储结果字符串，长度最多为n

相关题目