向字符串添加空格 图解题解

空格该插在哪，插完长什么样

给一个下标从 0 开始的字符串 s，再给一个下标数组 spaces，里面的下标从小到大排、彼此不重复。spaces 里每个下标处的字符之前，都要插进一个空格，返回插好的新串。题面例子 s 是 AlgoMoocOJ、spaces 是 [4,8]，在下标 4 的 M 前、下标 8 的 O 前各补一个空格，得到 Algo Mooc OJ。

遇一个空格就切一次串，账怎么算

照字面来：每碰到一个 spaces 下标，就在原串那里切开、插进一个空格。spaces 有 m 个下标就切 m 次，而字符串不可变，每切一次都要复制整条串，长 n 的串复制一趟就是 n 次搬运。切 m 次、每次搬 n 个字符，总代价是 O(n×m)，串一长就拖。

spaces 升序这条件，能省下什么

既然 spaces 从小到大排好，下一个要插空格的位置永远在当前位置右边、绝不回头。那就不必反复回原串切来切去，只要从左到右扫一遍 s，攥一个 j 指着 spaces 里下一个待插入的下标：扫到的字符下标要么还没够到 spaces[j]，要么正好等于它。两个各扫一条数据的指针，i 走 s、j 走 spaces，把插空格和放字符对齐。

一趟扫下来，每个字符先做哪件事

备一个可变容器（能往后追加、不用重建的列表或 StringBuilder）当答案。i 从 0 扫到串尾，每落到字符 c 先问：j 没走完 spaces、且 i 等于 spaces[j]？成立就先塞一个空格、j 前移一格；不管补没补，都无条件把 c 追加进去。i 走完，碎片拼成串就是答案。顺序不能反，先补空格再放字符。

AlgoMoocOJ、spaces=[4,8] 逐格过每步

s 是 AlgoMoocOJ，下标 0 到 9，spaces 是 [4,8]，j 从 0 起。i 从 0 走到 3 都不等于 spaces[0]，A、l、g、o 挨个进容器，攒成 Algo。

i 到 4 命中 spaces[0]：塞空格、j 到 1、放 M，成 Algo M。i 走 5、6、7 都不命中，o、o、c 追加成 Algo Mooc。i 到 8 命中 spaces[1]：塞空格、j 到 2、放 O，得 Algo Mooc O。i 到 9 时 spaces 已用尽，守卫不成立，跳过补空格直接放 J，成 Algo Mooc OJ。

取 spaces[j] 前不看 j，串一扫完就崩

取 spaces[j] 之前得先确认 j 没走出 spaces：用完后 j 等于它的长度，再读 spaces[j] 就摸到数组外面，越界会报错或读到脏值，守卫必须挡在取值前。空格落点也松不得，题目要在触发字符之前插，塞到后面整条串就错位。攒答案别用加号在循环里硬拼不可变字符串，每加一次都重建整串、代价滚回 O(n×m)；切片重建整串是同一个坑，一遍扫描追加才线性。

扫描只碰每个字符一次，i 单遍走、j 只增不减，前移总次数不超过 spaces 长度，时间 O(n)；答案串比原串多 m 个空格，长度 n 加 m 量级，空间 O(n)，辅助只用两个下标是 O(1)。

Python

from __future__ import annotations
from typing import *
from collections import *
from functools import *
from itertools import *
from math import *
from heapq import *
from bisect import *
class Solution:
    def addSpaces(self, s: str, spaces: List[int]) -> str:
        ans = []
        j = 0
        for i, c in enumerate(s):
            if j < len(spaces) and i == spaces[j]:
                ans.append(' ')
                j += 1
            ans.append(c)
        return ''.join(ans)

C++

#include <algorithm>
#include <array>
#include <cctype>
#include <climits>
#include <cmath>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
class Solution {
public:
    string addSpaces(string s, vector<int>& spaces) {
        string ans = "";
        for (int i = 0, j = 0; i < s.size(); ++i) {
            if (j < spaces.size() && i == spaces[j]) {
                ans += ' ';
                ++j;
            }
            ans += s[i];
        }
        return ans;
    }
};

Java

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