[LeetCode] 每日一题 2109. 向字符串添加空格（双指针 + 字符串操作）

题目链接

https://leetcode.cn/problems/adding-spaces-to-a-string

题目描述

给你一个下标从 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 中的所有值 严格递增

解题思路

本题的核心是 在指定位置插入空格，虽然整体逻辑不复杂，但在实现时有一些值得优化的细节

1. Java 字符串不可变，使用 StringBuilder

Java 的 String 本质上是一个 不可变的 char 数组，由 private final 修饰，任何修改操作都会创建新的字符串对象，带来额外的性能消耗
因此，我们选择 StringBuilder 作为拼接工具，并在初始化时直接预留 s.length() + spaces.length 的容量，避免动态扩展带来的性能开销

2. 避免数组插入操作，使用双指针优化

在 Java 里，数组的插入操作 平均复杂度是 O(n)，如果直接在 s 里插入空格，会涉及 数据搬移，导致性能下降
所以，我们使用 双指针 来高效构造最终字符串：

• 指针 i 遍历字符串 s，负责按顺序添加字符

• 指针 index 记录 spaces 数组中的插入位置，确保空格能在正确的位置插入

这样，每个字符最多访问一次，整体时间复杂度 O(n)，不会出现重复遍历或额外的插入开销

3. 为什么不推荐字符串拆分拼接？

另一种做法是 按 spaces 位置拆分字符串，再拼接，但这种方式会创建 多个字符串对象，导致 更多的内存占用 和 额外的垃圾回收。
虽然 Java 对 String 拼接有优化（如 String.concat() 可能转为 StringBuilder.append()），但相比 一次遍历构造完整字符串，仍然是 没必要的额外消耗

综合来看，双指针 + StringBuilder 方案是最优解，既能减少额外对象创建，又能优化性能

代码实现

class Solution {
    public String addSpaces(String s, int[] spaces) {
        StringBuilder ans = new StringBuilder(s.length() + spaces.length);
        int index = 0;
        for (int i = 0; i < s.length(); i++) {
            if (index < spaces.length && i == spaces[index]) {
                index++;
                ans.append(' ');
            }
            ans.append(s.charAt(i));
        }
        return ans.toString();
    }
}

复杂度分析

• 时间复杂度：O(n) ⏳

  • 每个字符最多访问一次，因此时间复杂度为 O(n)

• 空间复杂度：O(n) 💾

  • 结果字符串存入 StringBuilder，最终转换为 String，占用 O(n) 额外空间

总结

✅ 字符串不可变性：使用 StringBuilder 预分配容量，避免动态扩展带来的额外开销
✅ 双指针优化：避免在原字符串中插入，减少数据搬移，提高效率
✅ 避免字符串拆分拼接：减少 String 对象创建，降低内存占用，提高整体性能

希望这篇分享能为你带来启发！如果你有任何问题或建议，欢迎在评论区留言，与我共同交流探讨。