向字符串添加空格

标签: 数组 双指针 字符串 模拟

难度: Medium

给你一个下标从 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 中的所有值 严格递增

Submission

运行时间: 68 ms

内存: 46.5 MB

class Solution:
    def addSpaces(self, s: str, spaces: List[int]) -> str:
        i=0
        ans=[]
        for j in spaces:
            ans.append(s[i:j])
            i=j
        else:
            ans.append(s[j:])
            

        return " ".join(ans)

Explain

此题解采用了遍历加分割的方法来在字符串中插入空格。首先定义一个指针i初始化为0，用以指向当前字符串s的开始位置。然后对于spaces中的每个位置j，将`s[i:j]`（即从当前位置i到下一个空格位置j的子字符串）添加到结果列表`ans`中，然后更新i为当前位置j。遍历结束后，将最后一个位置到字符串末尾的部分`s[j:]`添加到`ans`中。最后，使用`join`函数以空格为分隔符合并`ans`列表中的所有子字符串，从而得到最终结果。

时间复杂度: O(n)

空间复杂度: O(n)

class Solution:
    def addSpaces(self, s: str, spaces: List[int]) -> str:
        i = 0  # 初始位置i
        ans = []  # 结果列表，存储分割后的子字符串
        for j in spaces:  # 遍历每个需要插入空格的位置j
            ans.append(s[i:j])  # 添加从i到j（不包括j）的子字符串到结果列表
            i = j  # 更新i为当前位置j
        ans.append(s[j:])  # 循环结束后，添加最后一部分子字符串
        return ' '.join(ans)  # 使用空格将所有子字符串合并为一个字符串

Explore

在实现中，如果`spaces`数组中的某个值j超出了字符串s的长度，那么`s[i:j]`将尝试访问s中不存在的部分，这会导致s的切片操作返回一个空字符串。因此，函数不会因此抛出异常，但会影响最终结果的正确性。为了避免这种情况，应当在实现前确保`spaces`中的所有值都在s的有效索引范围内，即所有的j都应小于等于s的长度。可以通过添加一个预处理步骤来移除那些超出s长度的索引。

题解假设`spaces`数组是有序的，且每个元素都唯一。如果`spaces`未排序，子字符串的截取将不按照原始字符串s的顺序进行，导致在结果字符串中单词顺序错误或重叠。因此，在实现前应确保`spaces`数组是按升序排列的。如果输入未排序，可以通过调用排序算法（如`spaces.sort()`）来预处理`spaces`。

在Python中，使用`for j in spaces:`循环后，变量`j`会保持循环结束时的值，因此在循环外部仍然可以访问它。这意味着，可以直接使用`ans.append(s[j:])`来添加最后一部分子字符串。如果在其他一些编程语言中这样做是不合法的，或者要避免潜在的错误，可以在循环内部记录最后一个有效的`j`，或在循环结束后使用`spaces[-1]`来获取最后一个插入点的索引。

使用列表`ans`逐步构建然后通过`join`合并的方法，主要优势在于效率。在Python中，字符串是不可变的，直接在字符串上进行拼接操作（如使用`+`或`+=`）会导致频繁的内存分配和字符串复制，从而增加时间和空间复杂度。而列表的拼接操作则相对高效，只有在最终执行`join`时才会创建一个完整的字符串。这个方法的劣势是需要额外的空间来存储列表，且逻辑上稍微复杂一些。但在处理大量字符串数据时，这种方法通常是更优的选择。