2109. 向字符串添加空格

🟠   🔖  数组 双指针 字符串 模拟  🔗 力扣 LeetCode

题目

You are given a 0-indexed string s and a 0-indexed integer array spaces that describes the indices in the original string where spaces will be added. Each space should be inserted before the character at the given index.

• For example, given s = "EnjoyYourCoffee" and spaces = [5, 9], we place spaces before 'Y' and 'C', which are at indices 5 and 9 respectively. Thus, we obtain "Enjoy Your Coffee".

Return the modified string after the spaces have been added.

Example 1:

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

Output: "Leetcode Helps Me Learn"

Explanation:

The indices 8, 13, and 15 correspond to the underlined characters in "Leetcode Helps Me Learn".

We then place spaces before those characters.

Example 2:

Input: s = "icodeinpython", spaces = [1,5,7,9]

Output: "i code in py thon"

Explanation:

The indices 1, 5, 7, and 9 correspond to the underlined characters in "i code in py thon".

We then place spaces before those characters.

Example 3:

Input: s = "spacing", spaces = [0,1,2,3,4,5,6]

Output: " s p a c i n g"

Explanation:

We are also able to place spaces before the first character of the string.

Constraints:

• 1 <= s.length <= 3 * 10^5
• s consists only of lowercase and uppercase English letters.
• 1 <= spaces.length <= 3 * 10^5
• 0 <= spaces[i] <= s.length - 1
• All the values of spaces are strictly increasing.

题目大意

给你一个下标从 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 对应 "Leetcode Helps Me Learn" 中加粗斜体字符。

接着在这些字符前添加空格。

示例 2：

输入： s = "icodeinpython", spaces = [1,5,7,9]

输出： "i code in py thon"

解释：

下标 1、5、7 和 9 对应 "i code in py thon" 中加粗斜体字符。

接着在这些字符前添加空格。

示例 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. 初始化变量：

   • res：用于存储最终结果的字符串。
   • left：记录当前片段的起始索引，初始化为 0。

2. 遍历 spaces 数组：

   • 每个 right 表示需要插入空格的索引位置。
   • 使用 slice(left, right) 提取从 left 到 right 的字符串片段，将其添加到 res 中，并在末尾加上一个空格。
   • 更新 left 为 right，准备提取下一片段。

3. 处理剩余部分：

   • 遍历完成后，left 指向最后一个未处理的片段起始位置。
   • 使用 slice(left) 提取剩余部分并拼接到结果字符串中。

4. 返回结果：拼接后的字符串即为答案。

复杂度分析

• 时间复杂度：O(n)
  • 每次 slice 操作的时间复杂度为 O(k)，其中 k 是每次截取的片段长度。
  • 整体 slice 操作总共处理 n 个字符（字符串长度），时间复杂度为 O(n)。
  • 遍历 spaces 的复杂度为 O(m)，其中 m 是 spaces 的长度。
  • 因此总时间复杂度为 O(n)。
• 空间复杂度：O(n)，使用一个结果字符串 res。

代码

/**
 * @param {string} s
 * @param {number[]} spaces
 * @return {string}
 */
var addSpaces = function (s, spaces) {
	let res = ''; // 初始化结果字符串
	let left = 0; // 当前片段的起始索引

	for (let right of spaces) {
		// 遍历插入空格的位置
		res += s.slice(left, right) + ' '; // 提取当前片段并加上空格
		left = right; // 更新起始索引
	}

	res += s.slice(left); // 处理剩余部分
	return res; // 返回结果字符串
};