劍指OFFER-替換空格

• Question
• Solution
• • 原字元串替換

Question

請實作一個函數，将一個字元串中的每個空格替換成“%20”。例如，當字元串為We Are Happy.則經過替換之後的字元串為We%20Are%20Happy。

關鍵詞：字元串 替換

Solution

原字元串替換

從前往後計算空格數，從後往前替換空格，保證每個字元隻移動一次。

時間複雜度： O(N)

空間複雜度：O(1)

• Python

## Python中String類型不可改變數值，隻能拼接
def replaceSpace(self, s):
    count = 0
    l = len(s)
    for a in s:
        if a==' ':
            count += 1
            s += '  '
    for i in range(l-1, -1, -1):
        if s[i] != ' ':
            s = s[:i+count*2] + s[i] + s[i+count*2+1:]
        else:
            count -= 1
            s = s[:i+count*2] + '%20' + s[i+count*2+3:]
    return s
           

• C++

void replaceSpace(char *str,int length) {
        int count = 0;
        for(int i=0; i< length; i++){
            if (str[i]==' ')
                count++;
        };
        for(int i=length-1; i>=0; i--){
            if(str[i]==' '){
                count--;
                str[i+count*2] = '%';
                str[i+count*2+1] = '2';
                str[i+count*2+2] = '0';
            }
            else
                str[i+count*2] = str[i];
        };
	}