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

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

问题陈述 − 我们有一个长度为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)。

空间复杂度 − 当我们用空格初始化finalStr时，空间复杂度为O(N + K)。

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