标签： 字符串

目标

给你一个下标从 0 开始的字符串 s ，以及一个下标从 0 开始的整数数组 spaces 。

数组 spaces 描述原字符串中需要添加空格的下标。每个空格都应该插入到给定索引处的字符值 之前 。

• 例如，s = "EnjoyYourCoffee" 且 spaces = [5, 9] ，那么我们需要在 'Y' 和 'C' 之前添加空格，这两个字符分别位于下标 5 和下标 9 。因此，最终得到 "Enjoy Your Coffee" 。

请你添加空格，并返回修改后的字符串。

示例 1：

输入：s = "LeetcodeHelpsMeLearn", spaces = [8,13,15]
输出："Leetcode Helps Me Learn"
解释：
下标 8、13 和 15 对应 "LeetcodeHelpsMeLearn" 中加粗斜体字符。
接着在这些字符前添加空格。

示例 2：

输入：s = "icodeinpython", spaces = [1,5,7,9]
输出："i code in py thon"
解释：
下标 1、5、7 和 9 对应 "icodeinpython" 中加粗斜体字符。
接着在这些字符前添加空格。

示例 3：

输入：s = "spacing", spaces = [0,1,2,3,4,5,6]
输出：" s p a c i n g"
解释：
字符串的第一个字符前可以添加空格。

说明：

• 1 <= s.length <= 3 * 10^5
• s 仅由大小写英文字母组成
• 1 <= spaces.length <= 3 * 10^5
• 0 <= spaces[i] <= s.length - 1
• spaces 中的所有值 严格递增

思路

在字符串的指定位置添加空格。

代码

/**
 * @date 2025-03-30 0:08
 */
public class AddSpaces2109 {

    public String addSpaces(String s, int[] spaces) {
        StringBuilder sb = new StringBuilder(s.length() + spaces.length);
        int start = 0;
        for (int i : spaces) {
            sb.append(s, start, i).append(' ');
            start = i;
        }
        sb.append(s.substring(start));
        return sb.toString();
    }
}

性能

目标

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

思路

当输入i的时候，之前所有的输入都需要反转，i字符本身不显示。使用split无法处理连续为i以及结尾为i的情况。

最直接的做法就是模拟操作，但是反转字符串的复杂度较高。考虑使用双端队列，当反转时，相当于从队首加入字符，从队尾开始读取。

代码

/**
 * @date 2024-04-01 8:42
 */
public class FinalString2810 {
    public String finalString_v1(String s) {
        StringBuilder res = new StringBuilder();
        Deque<Character> q = new ArrayDeque<>();
        boolean reverse = false;
        for (int i = 0; i < s.length(); i++) {
            char ch = s.charAt(i);
            if ('i' == ch) {
                reverse = !reverse;
            } else if (reverse) {
                q.push(ch);
            } else {
                q.offer(ch);
            }
        }
        Iterator<Character> it;
        if (reverse) {
            it = q.descendingIterator();
        } else {
            it = q.iterator();
        }
        while (it.hasNext()) {
            res.append(it.next());
        }
        return res.toString();
    }

    public String finalString(String s) {
        StringBuilder res = new StringBuilder();
        char[] chars = s.toCharArray();
        for (int i = 0; i < chars.length; i++) {
            if ('i' == chars[i]) {
                res.reverse();
            } else {
                res.append(chars[i]);
            }
        }
        return res.toString();
    }
}

性能

按道理来说应该是finalString_v1更快一些，res.reverse()时间复杂度是 O(n/2)，会将元素左右互换。但是leetcode显示的用时分布反而finalString更快，耗时是finalString_v1的一半2ms，应该与数据规模有关吧，字符串长度最大才100。finalString_v1有更多的流程控制，还体现不出性能。