Question

2810. 故障键盘

English Version

题目描述

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

解法

方法一：模拟

我们直接模拟键盘的输入过程，用一个字符数组 $t$ 来记录屏幕上的文本，初始时 $t$ 为空。

对于字符串 $s$ 中的每个字符 $c$，如果 $c$ 不是字符 $'i'$，那么我们将 $c$ 加入到 $t$ 的末尾；否则我们将 $t$ 中的所有字符反转。

最终答案即为 $t$ 中的字符组成的字符串。

时间复杂度 $O(n^2)$，空间复杂度 $O(n)$。其中 $n$ 是字符串 $s$ 的长度。

class Solution:
  def finalString(self, s: str) -> str:
    t = []
    for c in s:
      if c == "i":
        t = t[::-1]
      else:
        t.append(c)
    return "".join(t)

class Solution {
  public String finalString(String s) {
    StringBuilder t = new StringBuilder();
    for (char c : s.toCharArray()) {
      if (c == 'i') {
        t.reverse();
      } else {
        t.append(c);
      }
    }
    return t.toString();
  }
}

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

func finalString(s string) string {
  t := []rune{}
  for _, c := range s {
    if c == 'i' {
      for i, j := 0, len(t)-1; i < j; i, j = i+1, j-1 {
        t[i], t[j] = t[j], t[i]
      }
    } else {
      t = append(t, c)
    }
  }
  return string(t)
}

function finalString(s: string): string {
  const t: string[] = [];
  for (const c of s) {
    if (c === 'i') {
      t.reverse();
    } else {
      t.push(c);
    }
  }
  return t.join('');
}

impl Solution {
  pub fn final_string(s: String) -> String {
    let mut t = Vec::new();
    for c in s.chars() {
      if c == 'i' {
        t.reverse();
      } else {
        t.push(c);
      }
    }
    t.into_iter().collect()
  }
}