# 2109. Adding Spaces to a String
[2109. Adding Spaces to a String](https://leetcode.com/problems/adding-spaces-to-a-string) (<font color="#FFB800"> Medium</font> 通過率: 69.5%)

## 限制條件
<ul>
<li>1 &lt;= s.length &lt;= 3 * 10^5</li>
<li>s consists only of lowercase and uppercase English letters.</li>
<li>1 &lt;= spaces.length &lt;= 3 * 10^5</li>
<li>0 &lt;= spaces[i] &lt;= s.length - 1</li>
</ul>

### 解法 1
第一種方法是用 insert ，但不會過(TLE)，我不確定為什麼，可能這種方法太花時間了

- 時間複雜度: O(n)
- 空間複雜度: O(n)

class Solution {
public:
    string addSpaces(string s, vector<int>&amp; spaces) {
        int offset = 0;
        for(auto&amp; space : spaces) {
            s.insert(s.begin() + space + offset, ' ');
            offset++;
        }
        return s;
    }
};

### 解法 2
第二種方法用 push_back() 的方式去做，這樣就過了😅😅

- 時間複雜度: O(n)
- 空間複雜度: O(n)

class Solution {
public:
    string addSpaces(string s, vector<int>&amp; spaces) {
        string result;
        int space_index = 0;
        int size = spaces.size();
        for (int i = 0; i &lt; s.size(); i++) {
            if (space_index &lt; size &amp;&amp; spaces[space_index] == i) {
                space_index++;
                result.push_back(' ');
            }
            result.push_back(s[i]);
        }
        return result;
    }
};

### 解法 3
是第二種的加強，可以稍微再快一點點，利用預先規定result 字串的大小，可以減少一點記憶體的空間

- 時間複雜度: O(n)
- 空間複雜度: O(n)

class Solution {
public:
    string addSpaces(string s, vector<int>&amp; spaces) {
        int n = s.size();
        int totalSpaces = spaces.size();
        int newSize = n + totalSpaces;
        string result(newSize, ' '); 
        
        int s_index = n - 1;            
        int result_index = newSize - 1;
        int space_index = totalSpaces - 1;

        while (s_index &gt;= 0) {
            if (space_index &gt;= 0 &amp;&amp; s_index == spaces[space_index] - 1) {
                result[result_index--] = ' ';
                space_index--;
            }
            result[result_index--] = s[s_index--];  
        }
        return result;
    }
};