2109. Adding Spaces to a String

難度: Medium

類型: Array, Two Pointers, String, Simulation

C程式下載: 2109.c

前情題要:

給定一個字串, 另外給一個陣列告訴我們在哪裡加上空格。回傳處理好的字串。

You are given a 0-indexed string s and a 0-indexed integer array spaces that describes the indices in the original string where spaces will be added. Each space should be inserted before the character at the given index.

• For example, given s = "EnjoyYourCoffee" and spaces = [5, 9], we place spaces before 'Y' and 'C', which are at indices 5 and 9 respectively. Thus, we obtain "Enjoy Your Coffee".

Return the modified string after the spaces have been added.

 

Example 1:

Input: s = "LeetcodeHelpsMeLearn", spaces = [8,13,15]
Output: "Leetcode Helps Me Learn"
Explanation: 
The indices 8, 13, and 15 correspond to the underlined characters in "LeetcodeHelpsMeLearn".
We then place spaces before those characters.

Example 2:

Input: s = "icodeinpython", spaces = [1,5,7,9]
Output: "i code in py thon"
Explanation:
The indices 1, 5, 7, and 9 correspond to the underlined characters in "icodeinpython".
We then place spaces before those characters.

Example 3:

Input: s = "spacing", spaces = [0,1,2,3,4,5,6]
Output: " s p a c i n g"
Explanation:
We are also able to place spaces before the first character of the string.

 

Constraints:

• 1 <= s.length <= 3 * 105
• s consists only of lowercase and uppercase English letters.
• 1 <= spaces.length <= 3 * 105
• 0 <= spaces[i] <= s.length - 1
• All the values of spaces are strictly increasing.

思考方式:

1. 新的字串陣列長度是原本字串長度(不含結尾'\0'), 加上空格個數, 加1 (字串結尾'0')。

2. 逐個算好位置拷貝到新字串的對應位置上。

複雜度思考:

Time Complexity: O( 空格個數+分段memcpy ) 

Space Complexity: O( x )

結果:

Runtime: 3 ms, Beats: 86.67%

Memory: 27.88 MB, Beats: 100%

Accepted

66 / 66 testcases passed

tendchen

submitted at Jun 19, 2025 10:36

Runtime

3ms

Beats86.67%

Analyze Complexity

Memory

27.88MB

Beats100.00%

Analyze Complexity

Code

C

char* addSpaces(char* s, int* spaces, int spacesSize) {
    char *output_str;
    int output_str_len,current_output_index=0,i,last_space=0;

    output_str_len=strlen(s)+spacesSize+1;
    //printf("strlen(s)=%d,spacesSize=%d\n",strlen(s),spacesSize);
    output_str=malloc(output_str_len);
    //memset(output_str,0x20,output_str_len-1);
    output_str[strlen(s)+spacesSize]='\0';
    //printf("output_str_len=%d\n",output_str_len);
    //printf("output_str=%s\n",output_str);
    //printf("output_str=%s1234\n",output_str);
    for (i=0;i<spacesSize;i++)
    {
        //printf("(i=%d)current_output_index=%d\n",i,current_output_index);

        memcpy(output_str+current_output_index,s+last_space,spaces[i]-last_space);
        
        current_output_index=current_output_index+(spaces[i]-last_space);
        output_str[current_output_index]=' ';
        current_output_index++;
        last_space=spaces[i];
        //printf("(1)current_output_index=%d\n",current_output_index);
        //printf("output_str=%s\n",output_str);
        if (i==(spacesSize-1))
        {
            memcpy(output_str+current_output_index,s+last_space,strlen(s)-spaces[i]);   
        }
        //printf("(2)current_output_index=%d\n",current_output_index);
        //printf("output_str=%s\n",output_str);
    }
    //printf("output_str[%d]=%d\n",output_str_len-2,output_str[output_str_len-2]);
    //printf("output_str[%d]=%d\n",output_str_len-1,output_str[output_str_len-1]);
    return output_str;
}