在給定字串的特定位置新增空格後生成字串

---

在這個問題中，我們需要在字串中給定索引之前新增空格。我們可以使用兩種不同的方法來解決問題。第一種方法移動給定字串的字元，在特定索引處新增空格，第二種方法用空格替換預初始化字串的字元。

問題陳述 - 我們給定一個長度為 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。

第二種解決方案在時間複雜度方面得到了更好的最佳化，因為它一起遍歷列表和字串。第一種方法為列表的每個元素遍歷字串。程式設計師還可以嘗試在字串索引之後插入空格，而不是在字串索引之前。