题目描述
思路解析动画文字版
记牢这一句:i 扫字符,j 追下一个要插空格的位置,i 撞上 spaces[j] 就先补一个空格再把字符追进去。整趟只扫一遍,又快又稳。下面从头开始拼。
开工布局 · i 从 0 开始,ans 还空着：布局摆好。上面这条是原串 AlgoMoocOJ,每个格子下面是它的下标。右边面板是 spaces 数组,现在 j 指着第 0 行、值是 4,意思是下一个要在它前面补空格的位置是下标 4。下面这行 ans 是我们要拼的答案,现在还空着。指针 i 从 0 出发。
看 i=0 · 该不该在它前面补空格：指针 i 走到 0,和 spaces[0] 也就是 4 比一比,0 不等于 4,说明这个位置前面不用加空格。那就跳过补空格这步,直接去追加字符。
追加 s[0]=A 进 ans：不管刚才插没插空格,当前字符 A 都要放进答案。把它追加到 ans 末尾,现在答案变成了 「A」。这一格处理完,指针 i 往右挪一步,去看下一个字符。
看 i=1 · 该不该在它前面补空格：指针 i 走到 1,和 spaces[0] 也就是 4 比一比,1 不等于 4,说明这个位置前面不用加空格。那就跳过补空格这步,直接去追加字符。
追加 s[1]=l 进 ans：不管刚才插没插空格,当前字符 l 都要放进答案。把它追加到 ans 末尾,现在答案变成了 「Al」。这一格处理完,指针 i 往右挪一步,去看下一个字符。
看 i=2 · 该不该在它前面补空格：指针 i 走到 2,和 spaces[0] 也就是 4 比一比,2 不等于 4,说明这个位置前面不用加空格。那就跳过补空格这步,直接去追加字符。
追加 s[2]=g 进 ans：不管刚才插没插空格,当前字符 g 都要放进答案。把它追加到 ans 末尾,现在答案变成了 「Alg」。这一格处理完,指针 i 往右挪一步,去看下一个字符。
看 i=3 · 该不该在它前面补空格：指针 i 走到 3,和 spaces[0] 也就是 4 比一比,3 不等于 4,说明这个位置前面不用加空格。那就跳过补空格这步,直接去追加字符。
追加 s[3]=o 进 ans：不管刚才插没插空格,当前字符 o 都要放进答案。把它追加到 ans 末尾,现在答案变成了 「Algo」。这一格处理完,指针 i 往右挪一步,去看下一个字符。
看 i=4 · 该不该在它前面补空格：指针 i 走到 4,拿它和 spaces[0] 也就是 4 比一比,正好相等,命中了!这说明当前字符 M 之前该补一个空格。先别急着放字符,下一步先把空格补上。
命中!在 s[4]=M 之前补一个空格：命中了就先补空格。往 ans 末尾放一个空格,你看答案串在字符 M 之前多了一个空格。补完把 j 往后挪一格,从 0 变成 1,面板高亮跟着移到下一个待插入的位置(下标 8)。空格补好了,接着才轮到字符。
追加 s[4]=M 进 ans：不管刚才插没插空格,当前字符 M 都要放进答案。把它追加到 ans 末尾,现在答案变成了 「Algo M」。这一格处理完,指针 i 往右挪一步,去看下一个字符。
看 i=5 · 该不该在它前面补空格：指针 i 走到 5,和 spaces[1] 也就是 8 比一比,5 不等于 8,说明这个位置前面不用加空格。那就跳过补空格这步,直接去追加字符。
追加 s[5]=o 进 ans：不管刚才插没插空格,当前字符 o 都要放进答案。把它追加到 ans 末尾,现在答案变成了 「Algo Mo」。这一格处理完,指针 i 往右挪一步,去看下一个字符。
看 i=6 · 该不该在它前面补空格：指针 i 走到 6,和 spaces[1] 也就是 8 比一比,6 不等于 8,说明这个位置前面不用加空格。那就跳过补空格这步,直接去追加字符。
追加 s[6]=o 进 ans：不管刚才插没插空格,当前字符 o 都要放进答案。把它追加到 ans 末尾,现在答案变成了 「Algo Moo」。这一格处理完,指针 i 往右挪一步,去看下一个字符。
看 i=7 · 该不该在它前面补空格：指针 i 走到 7,和 spaces[1] 也就是 8 比一比,7 不等于 8,说明这个位置前面不用加空格。那就跳过补空格这步,直接去追加字符。
追加 s[7]=c 进 ans：不管刚才插没插空格,当前字符 c 都要放进答案。把它追加到 ans 末尾,现在答案变成了 「Algo Mooc」。这一格处理完,指针 i 往右挪一步,去看下一个字符。
看 i=8 · 该不该在它前面补空格：指针 i 走到 8,拿它和 spaces[1] 也就是 8 比一比,正好相等,命中了!这说明当前字符 O 之前该补一个空格。先别急着放字符,下一步先把空格补上。
命中!在 s[8]=O 之前补一个空格：命中了就先补空格。往 ans 末尾放一个空格,你看答案串在字符 O 之前多了一个空格。补完把 j 往后挪一格,从 1 变成 2,这下 spaces 里两个下标都用过了、j 已用完,后面不再有待插入的位置,面板高亮也随之撤掉。空格补好了,接着才轮到字符。
追加 s[8]=O 进 ans：不管刚才插没插空格,当前字符 O 都要放进答案。把它追加到 ans 末尾,现在答案变成了 「Algo Mooc O」。这一格处理完,指针 i 往右挪一步,去看下一个字符。
看 i=9 · 该不该在它前面补空格：指针 i 走到 9,看右边面板,j 已经等于 2,spaces 两个下标都用完了。既然没有待插入的位置了,就跳过检查,直接去追加这个字符。这一步演示的就是 j 用尽后的收尾。
追加 s[9]=J 进 ans：不管刚才插没插空格,当前字符 J 都要放进答案。把它追加到 ans 末尾,现在答案变成了 「Algo Mooc OJ」。这一格是原串最后一个字符,处理完 i 就到达串尾之后的位置,下一步进入扫描结束、开始收束。
扫描结束 · 答案拼好：整条串扫完了。回头看,我们只在两处补了空格:下标 4 的 M 前面、下标 8 的 O 前面,这两个触发字符标成了绿色。最后拼出来的答案就是 「Algo Mooc OJ」,和一开始说的 Algo Mooc OJ 分毫不差。全程只扫了一遍,双指针配合得干净利落。
边界想清:空格可以补在最前面、也可以补在最后一个字符之前;每个 spaces 值都落在有效下标内,严格递增不会重复。
面试重点:双指针单遍、命中先补空格再追加、用可变容器攒串避免 O(n 方)、时间空间都是 O(n)。
参考代码
from __future__ import annotationsfrom 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)复杂度
- 时间：O(n)，n 是原串长度。i 从头扫到尾只走一遍,每个位置最多补一个空格加追加一个字符,都是常数操作;j 一路只增不减,总共前移的次数等于 spaces 的长度,不超过 n。合起来随 n 线性增长
- 空间：O(n)，按峰值算,主要花在攒出来的答案串上:它比原串多了 spaces 长度个空格,长度是 n 加 m 量级,也就是 O(n)。除答案外只用了 i、j 两个下标,额外辅助空间是 O(1)
易错点
面试追问把动画讲成自己的话
追问这题的核心思路一句话怎么说?
追问为什么要用可变容器攒答案,直接字符串相加不行吗?
追问时间和空间复杂度各是多少?
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
最少交换次数来组合所有的 1 II
LeetCode 2134 · 中等 · 沿着 双指针套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题