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

这道题到底在问什么

输入

s="LeetcodeHelpsMeLearn", spaces=[8,13,15]

输出

"Leetcode Helps Me Learn"

输入

s="AlgoMoocOJ", spaces=[4,8]

输出

"Algo Mooc OJ"

最优解：一步一步想明白

1. 3记牢这一句:i 扫字符,j 追下一个要插空格的位置,i 撞上 spaces[j] 就先补一个空格再把字符追进去。整趟只扫一遍,又快又稳。下面从头开始拼。
2. 4双指针待命布局摆好。上面这条是原串 AlgoMoocOJ,每个格子下面是它的下标。右边面板是 spaces 数组,现在 j 指着第 0 行、值是 4,意思是下一个要在它前面补空格的位置是下标 4。下面这行 ans 是我们要拼的答案,现在还空着。指针 i 从 0 出发。
3. 5比较 i 与 spaces[j]指针 i 走到 0,和 spaces[0] 也就是 4 比一比,0 不等于 4,说明这个位置前面不用加空格。那就跳过补空格这步,直接去追加字符。
4. 6追加当前字符不管刚才插没插空格,当前字符 A 都要放进答案。把它追加到 ans 末尾,现在答案变成了 「A」。这一格处理完,指针 i 往右挪一步,去看下一个字符。
5. 7比较 i 与 spaces[j]指针 i 走到 1,和 spaces[0] 也就是 4 比一比,1 不等于 4,说明这个位置前面不用加空格。那就跳过补空格这步,直接去追加字符。
6. 8追加当前字符不管刚才插没插空格,当前字符 l 都要放进答案。把它追加到 ans 末尾,现在答案变成了 「Al」。这一格处理完,指针 i 往右挪一步,去看下一个字符。
7. 9比较 i 与 spaces[j]指针 i 走到 2,和 spaces[0] 也就是 4 比一比,2 不等于 4,说明这个位置前面不用加空格。那就跳过补空格这步,直接去追加字符。
8. 10追加当前字符不管刚才插没插空格,当前字符 g 都要放进答案。把它追加到 ans 末尾,现在答案变成了 「Alg」。这一格处理完,指针 i 往右挪一步,去看下一个字符。
9. 11比较 i 与 spaces[j]指针 i 走到 3,和 spaces[0] 也就是 4 比一比,3 不等于 4,说明这个位置前面不用加空格。那就跳过补空格这步,直接去追加字符。
10. 12追加当前字符不管刚才插没插空格,当前字符 o 都要放进答案。把它追加到 ans 末尾,现在答案变成了 「Algo」。这一格处理完,指针 i 往右挪一步,去看下一个字符。
11. 13比较 i 与 spaces[j]指针 i 走到 4,拿它和 spaces[0] 也就是 4 比一比,正好相等,命中了!这说明当前字符 M 之前该补一个空格。先别急着放字符,下一步先把空格补上。
12. 14插空格 · j 前移命中了就先补空格。往 ans 末尾放一个空格,你看答案串在字符 M 之前多了一个空格。补完把 j 往后挪一格,从 0 变成 1,面板高亮跟着移到下一个待插入的位置(下标 8)。空格补好了,接着才轮到字符。
13. 15追加当前字符不管刚才插没插空格,当前字符 M 都要放进答案。把它追加到 ans 末尾,现在答案变成了 「Algo M」。这一格处理完,指针 i 往右挪一步,去看下一个字符。
14. 16比较 i 与 spaces[j]指针 i 走到 5,和 spaces[1] 也就是 8 比一比,5 不等于 8,说明这个位置前面不用加空格。那就跳过补空格这步,直接去追加字符。
15. 17追加当前字符不管刚才插没插空格,当前字符 o 都要放进答案。把它追加到 ans 末尾,现在答案变成了 「Algo Mo」。这一格处理完,指针 i 往右挪一步,去看下一个字符。
16. 18比较 i 与 spaces[j]指针 i 走到 6,和 spaces[1] 也就是 8 比一比,6 不等于 8,说明这个位置前面不用加空格。那就跳过补空格这步,直接去追加字符。
17. 19追加当前字符不管刚才插没插空格,当前字符 o 都要放进答案。把它追加到 ans 末尾,现在答案变成了 「Algo Moo」。这一格处理完,指针 i 往右挪一步,去看下一个字符。
18. 20比较 i 与 spaces[j]指针 i 走到 7,和 spaces[1] 也就是 8 比一比,7 不等于 8,说明这个位置前面不用加空格。那就跳过补空格这步,直接去追加字符。
19. 21追加当前字符不管刚才插没插空格,当前字符 c 都要放进答案。把它追加到 ans 末尾,现在答案变成了 「Algo Mooc」。这一格处理完,指针 i 往右挪一步,去看下一个字符。
20. 22比较 i 与 spaces[j]指针 i 走到 8,拿它和 spaces[1] 也就是 8 比一比,正好相等,命中了!这说明当前字符 O 之前该补一个空格。先别急着放字符,下一步先把空格补上。
21. 23插空格 · j 前移命中了就先补空格。往 ans 末尾放一个空格,你看答案串在字符 O 之前多了一个空格。补完把 j 往后挪一格,从 1 变成 2,这下 spaces 里两个下标都用过了、j 已用完,后面不再有待插入的位置,面板高亮也随之撤掉。空格补好了,接着才轮到字符。
22. 24追加当前字符不管刚才插没插空格,当前字符 O 都要放进答案。把它追加到 ans 末尾,现在答案变成了 「Algo Mooc O」。这一格处理完,指针 i 往右挪一步,去看下一个字符。
23. 25比较 i 与 spaces[j]指针 i 走到 9,看右边面板,j 已经等于 2,spaces 两个下标都用完了。既然没有待插入的位置了,就跳过检查,直接去追加这个字符。这一步演示的就是 j 用尽后的收尾。
24. 26追加当前字符不管刚才插没插空格,当前字符 J 都要放进答案。把它追加到 ans 末尾,现在答案变成了 「Algo Mooc OJ」。这一格是原串最后一个字符,处理完 i 就到达串尾之后的位置,下一步进入扫描结束、开始收束。
25. 27大功告成整条串扫完了。回头看,我们只在两处补了空格:下标 4 的 M 前面、下标 8 的 O 前面,这两个触发字符标成了绿色。最后拼出来的答案就是 「Algo Mooc OJ」,和一开始说的 Algo Mooc OJ 分毫不差。全程只扫了一遍,双指针配合得干净利落。

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

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)

#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;
    }
};

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();
    }
}

复杂度

面试官可能追问