문제 링크

내 코드

16ms, 85.74MB

class Solution {
public:
    string addSpaces(string s, vector<int>& spaces) {
        // spaces[i], spaces[i + 1]
        string answer = s.substr(0, spaces.front());
        answer.push_back(' ');
        for(int i{}, e{static_cast<int>(spaces.size()) - 1}; i < e; ++ i) {
            int start = spaces[i], finish = spaces[i + 1];
            answer += s.substr(start, finish - start);
            answer.push_back(' ');
        }
        answer += s.substr(spaces.back());
        return answer;
    }
};

Solution

Approach 1: Using Built-in Functions

• 27ms, 88.80MB
• Complexity
  • Let $n$ be the size of the string s, and m be the size of the array spaces, which represents the number of spaces to be added.
  • Time Complexity: $O(n + m)$
  • Space Complexity: $O(1)$ (if we only count auxiliary space) or $O(n+m)$ (if we count the space for the result)

class Solution {
public:
    string addSpaces(string s, vector<int>& spaces) {
        // Stream to dynamically construct the string
        stringstream result;
        int spaceIndex = 0;

        for (int stringIndex = 0; stringIndex < s.size(); ++stringIndex) {
            if (spaceIndex < spaces.size() &&
                stringIndex == spaces[spaceIndex]) {
                // Insert space at the correct position
                result << ' ';
                ++spaceIndex;
            }
            // Append the current character
            result << s[stringIndex];
        }
        // Convert the stream to a string
        return result.str();
    }
};

Approach 2: Two-Pointer Technique

• 20ms, 82.38MB
• Complexity
  • Let $n$ be the size of the string s, and m be the size of the array spaces, which represents the number of spaces to be added.
  • Time Complexity: $O(n + m)$
  • Space Complexity: $O(1)$ (if we only count auxiliary space) or $O(n+m)$ (if we count the space for the result)

class Solution {
public:
    string addSpaces(string s, vector<int>& spaces) {
        string result;
        // Pre-allocate space for efficiency
        result.reserve(s.size() + spaces.size());

        int spaceIndex = 0;
        for (int stringIndex = 0; stringIndex < s.size(); ++stringIndex) {
            if (spaceIndex < spaces.size() &&
                stringIndex == spaces[spaceIndex]) {
                // Insert space at the correct position
                result += ' ';
                ++spaceIndex;
            }
            // Append the current character
            result += s[stringIndex];
        }

        return result;
    }
};