在给定字符串的特定位置添加空格后生成字符串

---

在这个问题中，我们需要在字符串中给定索引之前添加空格。我们可以使用两种不同的方法来解决问题。第一种方法移动给定字符串的字符，在特定索引处添加空格，第二种方法用空格替换预初始化字符串的字符。

问题陈述 - 我们给定一个长度为 N 的字符串 str，其中包含字母数字字符。我们还给定了一个包含 M 个正整数的 spaceList 数组，表示字符串索引。我们需要在数组中存在的每个索引之前向字符串添加空格。之后，我们需要打印更新后的字符串。

示例

输入

str = "welcometotutorialspoint", spaceList = {7, 9}

输出

‘welcome to tutorialspoint’

说明 - 在这里，我们考虑基于 0 的索引。我们在输入字符串的第 7 个和第 9 个索引之前添加了空格。

输入

 str = “abc”, spaceList = {1, 2}

输出

‘a b c’

说明 - 我们在索引 1 和 2 之前添加了空格。

输入

str = "IloveCProgramming", spaceList = {1, 5, 6}

输出

I love C Programming

说明 - 我们通过在给定索引处添加空格来分隔字符串。

方法 1

在这种方法中，我们将从数组中获取一个特定索引。之后，我们将在字符串末尾添加空格，并将从当前索引到字符串末尾的所有字符向右移动 1 个位置。

算法

步骤 1 - 使用字符串的大小初始化 size 变量。

步骤 2 - 使用循环遍历字符串。

步骤 3 - 从 spaceList 数组中获取索引。

步骤 4 - 在给定字符串的末尾添加空格。

步骤 5 - 将所有 str[i+1] 字符替换为 str[i]。这里 'I' 从 'strLen' 开始，直到它等于索引 - 1。

步骤 6 - 将空格分配给 str[index - 1]。

步骤 7 - 最后，返回 str，它是一个更新后的字符串。

示例

#include <bits/stdc++.h>
using namespace std;

string AddSpaces(string str, vector<int> &spaceList) {
    // get the size of the list
    int size = spaceList.size();
    // traverse the space list
    while (size--) {
        // get index to add space
        int index = spaceList[size] + 1;
        int strLen = str.size() - 1;
        // append space at the end
        str += ' ';
        // Move space
        for (int i = strLen; i >= index - 1; i--) {
            str[i + 1] = str[i];
        }
        str[index - 1] = ' ';
    }
    return str;
}
int main() {
    string str = "welcometotutorialspoint";
    vector<int> spaceList = {7, 9};
    cout << "The updated string is : " << AddSpaces(str, spaceList) << endl;
    return 0;
}

输出

The updated string is : welcome to tutorialspoint

时间复杂度 - O(N*K)，其中 K 是列表的大小，N 是字符串的大小。

空间复杂度 - O(1)，因为我们修改了同一个字符串。

方法 2

在这种方法中，我们初始化一个字符串，其中包含等于字符串长度 + 列表长度的总空格。之后，我们通过用输入字符串的字符替换它来更新字符串，如果我们需要添加空格，则保持原样。

算法

步骤 1 - 使用空字符串初始化 'finalStr' 字符串。此外，字符串长度应等于 str_size 和 list_size。这里，str_size 是字符串的大小，list_size 是列表的大小。

步骤 2 - 遍历 finalStr 字符串。

步骤 3 - 如果 l_index 小于列表大小，并且 p 等于 spaceList[l_index] + l_index，则将 l_index 增加 1，因为我们需要在该位置添加空格。

步骤 4 - 否则，将 str[index] 分配给 finalStr[p] 并将 index 的值增加 1。

步骤 5 - 返回 'finalStr' 字符串。

示例

#include <bits/stdc++.h>
using namespace std;

string AddSpaces(string str, vector<int> &spaceList) {
    int str_size = str.size(), list_size = spaceList.size(), l_index = 0, s_index = 0;
    string finalStr(str_size + list_size, ' ');
    // Iterate over M+N length
    for (int p = 0; p < str_size + list_size; p++) {
        if (l_index < list_size and p == spaceList[l_index] + l_index)
            l_index++;
        else
            finalStr[p] = str[s_index++];
    }
    // Return the required string
    return finalStr;
}
int main() {
    string str = "welcometotutorialspoint";
    vector<int> spaceList = {7, 9};
    cout << "The updated string is : " << AddSpaces(str, spaceList) << endl;
    return 0;
}

输出

The updated string is : welcome to tutorialspoint

时间复杂度 - O(N + K)，因为我们一起遍历列表和字符串。

空间复杂度 - O(N + K)，因为我们使用空空格初始化 finalStr。

第二种解决方案在时间复杂度方面得到了更好的优化，因为它一起遍历列表和字符串。第一种方法为列表的每个元素遍历字符串。程序员还可以尝试在字符串索引之后插入空格，而不是在字符串索引之前。