向字符串添加空格

2109。向字符串添加空格

难度：中等

主题：数组、两个指针、字符串、模拟

给你一个 0 索引的字符串 s 和一个 0 索引的整数数组 space ，它描述了原始字符串中将添加空格的索引。每个空格都应插入在给定索引处的字符之前。

• 例如，给定 s = "EnjoyYourCoffee" 和 space = [5, 9]，我们在 'Y' 和 'C' 之前放置空格，它们分别位于索引 5 和 9 处。因此，我们获得了“享受你的咖啡”。

返回修改后的字符串添加空格后。

示例1：

• 输入： s = "LeetcodeHelpsMeLearn", 空格 = [8,13,15]
• 输出：“Leetcode 帮助我学习”
• 说明：索引8、13和15对应于“LeetcodeHelpsMeLearn”中的下划线字符。
  • 然后我们在这些字符之前放置空格。

示例2：

• 输入： s = "icodeinpython", 空格 = [1,5,7,9]
• 输出：“我在 py thon 中编码”
• 解释： 索引 1、5、7、9 对应于“icodeinpython”中带下划线的字符。
  • 然后我们在这些字符之前放置空格。

示例 3：

• 输入： s = "间距", 空格 = [0,1,2,3,4,5,6]
• 输出：“s p a c i n g”
• 说明：我们还可以在字符串的第一个字符之前放置空格。

约束：

• 1 5
• s 仅由小写和大写英文字母组成。
• 1 5
• 0
• 所有空格的值都严格递增。

提示：

1. 创建一个新字符串（最初为空）作为修改后的字符串。迭代原始字符串并将原始字符串的每个字符附加到新字符串。但是，每次遇到需要在其前面留有空格的字符时，请在附加该字符之前附加一个空格。
2. 由于空间位置的索引数组已排序，因此使用指针来跟踪下一个放置空间的索引。仅在附加空格后才增加指针。
3. 确保您的追加操作可以在 O(1) 内完成。

解决方案：

我们可以使用带有两个指针的有效方法。 PHP 5.6 中的实现如下所示：

解决方案说明：

1. 使用指针 spaceIndex 来跟踪 space 数组中的当前位置。
2. 使用循环遍历字符串 s。
3. 检查字符串中的当前索引是否与空格数组中的当前值匹配。如果是，则在结果后追加一个空格并将 spaceIndex 指针向前移动。
4. 将字符串的当前字符附加到结果中。
5. 以单个字符串的形式返回最终结果。

这种方法确保我们利用空格数组的排序顺序有效地处理输入。

让我们用 PHP 实现这个解决方案：2109。向字符串添加空格

<?php /**
 * @param String $s
 * @param Integer[] $spaces
 * @return String
 */
function addSpaces($s, $spaces) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Example 1
$s1 = "LeetcodeHelpsMeLearn";
$spaces1 = [8, 13, 15];
echo addSpaces($s1, $spaces1) . "\n"; // Output: "Leetcode Helps Me Learn"

// Example 2
$s2 = "icodeinpython";
$spaces2 = [1, 5, 7, 9];
echo addSpaces($s2, $spaces2) . "\n"; // Output: "i code in py thon"

// Example 3
$s3 = "spacing";
$spaces3 = [0, 1, 2, 3, 4, 5, 6];
echo addSpaces($s3, $spaces3) . "\n"; // Output: " s p a c i n g"
?>

解释：

1. 高效追加： . PHP 中的运算符用于高效地追加字符串。
2. 两个指针： spaceIndex 指针确保我们只处理一次 space 数组。
3. 时间复杂度：
   • 迭代字符串需要 O(n)，其中 n 是字符串的长度。
   • 检查空格数组指针需要 O(m)，其中 m 是空格数组的长度。
   • 组合：O(n·m)，在给定约束的情况下这是最佳的。

该解决方案遵守约束条件，即使对于大量输入也很有效。

联系链接

如果您发现本系列有帮助，请考虑在 GitHub 上给 存储库 一个星号或在您最喜欢的社交网络上分享该帖子？。您的支持对我来说意义重大！

如果您想要更多类似的有用内容，请随时关注我：

• 领英
• GitHub

以上是向字符串添加空格的详细内容。更多信息请关注PHP中文网其他相关文章！