Adding Spaces to a String[M,ArrayTwo Pointers,String,Simulation]

https://leetcode.com/problems/adding-spaces-to-a-string/description/

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. Python

class Solution:
    def addSpaces(self, s: str, spaces: List[int]) -> str:
        gap = 0
        for x in spaces:
            s = s[:x+gap] + " " + s[x+gap:]
            gap+=1
        return s

깔끔하게 답 잘 나오는구만,

또 테스트 케이스에서 input을 겁나게 길게 때려박아서 time limint을 건다 -_-

 

아오 이것들이 진짜!!

 

class Solution:
    def addSpaces(self, s: str, spaces: List[int]) -> str:
        ans = ""
        for i in range(len(s)):
            if i in spaces:
                ans+=" "
            ans += (s[i])
        return ans

 

얘도 타임오바;;

Ensure that your append operation can be done in O(1).

 

class Solution:
    def addSpaces(self, s: str, spaces: List[int]) -> str:
        ans = []
        prev_idx = 0
        for x in spaces:
            ans.append(s[prev_idx:x])
            ans.append(" ")
            prev_idx = x
        ans.append(s[prev_idx:])
        return "".join(ans)

 

이렇게 하면 S를 돌지 않고 spaces list만 돌아서 Time complexity가 O(1)이라칸다!

 

 

2. C

char* addSpaces(char* s, int* spaces, int spacesSize) {
    int s_len = strlen(s);
    int new_len = s_len + spacesSize;
    char* result = (char*)malloc((new_len+1)*sizeof(char));

    int s_idx = 0 ;
    int result_idx = 0;

    for(int i=0;i<spacesSize;i++){
        int space_idx = spaces[i];
        while(s_idx < space_idx){
            result[result_idx++] = s[s_idx++];
        }
        result[result_idx++] = ' ';
    }

    while(s[s_idx]!='\0'){
        result[result_idx++] = s[s_idx++];
    }

    result[result_idx] = '\0';
    return result;
}

 

진짜 주접을 떨었다.. index를 몇 개를 만든거냐..

char* addSpaces(char* s, int* spaces, int spacesSize) {
    char* result = (char*)malloc(strlen(s) + 1 + spacesSize);
    int cnt;
    int start = 0;
    int end = 0;

    for (cnt = 0; cnt < strlen(s); cnt++) {
        if (start < spacesSize  && spaces[start] == cnt) {
            result[end++] = ' ';
            start++;
        }
        result[end++] = s[cnt];
    }
    result[end] = '\0';

    return result;

 

index로 장난을 쳐야하는 이번 문제;;

char* addSpaces(char* s, int* spaces, int spacesSize) {
    int n = strlen(s);
    char* ans = (char*)malloc((spacesSize+n+1)*sizeof(char));
    int end = 0 ;
    int start = 0;

    for(int i = 0; i < n ; i++){
        if(start<spacesSize && spaces[start]==i){
            ans[end] = ' ';
            end++;
            start++;
        }
        ans[end] = s[i];
        end++;
    }
    ans[end] = '\0';
    return ans;
}

 

 

 

3. C++

C++에서 string 초기화는 string ans(10,' ') 요렇게 한다.

class Solution {
public:
    string addSpaces(string s, vector<int>& spaces) {
        int n = s.length();
        int sn = spaces.size();
        string ans(n+sn,' '); //이렇게 초기화 하는 것이다.

        int start = 0;
        int end = 0;
        for(int i=0;i<n;i++){
            if(start<sn && i==spaces[start]){
                ans[end++] = ' ';
                start++;
            }
            ans[end++] = s[i];
        }
        return ans;
    }
};

 

아.. 참고로 C++은 string 그냥 더하기도 된다.

 

C보다 훨 편하네 증말

 

class Solution {
public:
    string addSpaces(string s, vector<int>& spaces) {
        int n = s.length();
        int sn = spaces.size();
        string ans;
        int j = 0;
        for(int i=0;i<n;i++){
            if(j<sn && spaces[j]==i){
                ans+=" ";
                j++;
            }
            ans+=s[i];
        }
        return ans;
    }
};

 

Python에선 runtime 속도 문제, C는 허접한 Method가 문제..

 

C++이 그나마 절충점같다.