2109.向字符串添加空格：双指针

【LetMeFly】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 * 105
• s 仅由大小写英文字母组成
• 1 <= spaces.length <= 3 * 105
• 0 <= spaces[i] <= s.length - 1
• spaces 中的所有值 严格递增

方法一：直接插入

记录下插入了几个空格（每次插入一个空格原字符串长度会加一），遍历spaces数组的过程中，往字符串的$插入下标+已插入空格个数$的位置插入一个空格。

这样每次插入操作会导致插入位置后面的所有字符均向后移动一个位置，单次插入时间复杂度为$O(n)$。

• 时间复杂度$O(len(s)\times len(spaces))$
• 空间复杂度$O(1)$

但是C++能丝滑通过。

AC代码

C++

/*
 * @Author: LetMeFly
 * @Date: 2025-03-30 16:51:08
 * @LastEditors: LetMeFly.xyz
 * @LastEditTime: 2025-03-30 16:53:16
 * @Description: 可能会TLE的做法，试试C++字符串的insert
 */
#ifdef _WIN32
#include "_[1,2]toVector.h"
#endif

class Solution {
public:
    string addSpaces(string s, vector<int>& spaces) {
        int cnt = 0;
        for (int t : spaces) {
            s.insert(s.begin() + (cnt++ + t), ' ');
        }
        return s;
    }
};

C++字符串相关操作耗时测试

测试一下C++的向字符串前面位置插入元素、改变字符串前面位置某个字符、向字符串末尾添加元素的耗时

// g++ Codes\2109-adding-spaces-to-a-string_TestForTimeConsume.cpp -o temp.exe; ./temp.exe
// ./temp.exe
int main() {
    string s(100000, '0');
    time_t start = clock();
    for (int i = 0; i < 100000; i++) {
        s.insert(s.begin() + rand() % 10, rand() % 20);
    }
    time_t end = clock();
    cout << end - start << endl;  // 基本上280-290ms

    start = end;
    for (int i = 0; i < 100000; i++) {
        s[rand() % 10] = rand() % 20;  // 基本上3ms
    }
    end = clock();
    cout << end - start << endl;

    start = end;
    for (int i = 0; i < 100000; i++) {
        s += rand() % 20;    // 基本上2ms
    }
    end = clock();
    cout << end - start << endl;
    return 0;
}

可以发现向字符串前面插入元素确实较耗时。

方法二：双指针

一个指针遍历被插空格的字符串，一个指针指向空格数组。

遍历字符串的过程中，如果空格数组指针指向的空格下标和字符串下标相同，则往答案中添加一个空格。不论是否添加了空格，遍历过程中都要将当前字符加入答案中。

• 时间复杂度$O(len(s))$
• 空间复杂度：可变字符串如C++：$O(1)$；不可变字符串如Python/Golang/Java：$O(n)$

AC代码

C++

/*
 * @Author: LetMeFly
 * @Date: 2025-03-31 14:31:07
 * @LastEditors: LetMeFly.xyz
 * @LastEditTime: 2025-03-31 14:32:48
 */
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() && spaces[j] == i) {
                ans += ' ';
                j++;
            }
            ans += s[i];
        }
        return ans;
    }
};

C++

/*
 * @Author: LetMeFly
 * @Date: 2025-03-31 14:21:40
 * @LastEditors: LetMeFly.xyz
 * @LastEditTime: 2025-03-31 14:24:26
 */
class Solution {
private:
    inline bool isSpace(vector<int>& spaces, int i, int j) {
        if (j == spaces.size()) {
            return false;
        }
        return i == spaces[j];
    }
public:
    string addSpaces(string s, vector<int>& spaces) {
        string ans;
        for (int i = 0, j = 0; i < s.size(); i++) {
            if (isSpace(spaces, i, j)) {
                ans += ' ';
                j++;
            }
            ans += s[i];
        }
        return ans;
    }
};

Python

'''
Author: LetMeFly
Date: 2025-03-31 14:33:18
LastEditors: LetMeFly.xyz
LastEditTime: 2025-03-31 14:34:50
'''
from typing import List

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 spaces[j] == i:
                ans.append(' ')
                j += 1
            ans.append(c)
        return ''.join(ans)

Java

/*
 * @Author: LetMeFly
 * @Date: 2025-03-31 14:37:11
 * @LastEditors: LetMeFly.xyz
 * @LastEditTime: 2025-03-31 14:44:41
 */
import java.lang.StringBuffer;

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

Go

/*
 * @Author: LetMeFly
 * @Date: 2025-03-31 14:45:51
 * @LastEditors: LetMeFly.xyz
 * @LastEditTime: 2025-03-31 15:18:02
 */
package main

func addSpaces(s string, spaces []int) string {
    ans := make([]byte, 0, len(s) + len(spaces))
    j := 0
    for i, c := range s {
        if j < len(spaces) && spaces[j] == i {
            ans = append(ans, ' ')
            j++
        }
        ans = append(ans, byte(c))
    }
    return string(ans)
}

同步发文于CSDN和我的个人博客，原创不易，转载经作者同意后请附上原文链接哦~

千篇源码题解已开源