Microsoft - URLify A Given String

#easy

思路

如果想把這道題目做到極致，就不要只用額外的輔助空間了！

首先擴充數組到每個空格替換成"%20"之後的大小。

然後從後向前替換空格，也就是雙指針法，過程如下：

i指向新長度的末尾，j指向舊長度的末尾。

有同學問了，為什麼要從後向前填充，從前向後填充不行麼？

從前向後填充就是O(n^2)的算法了，因為每次添加元素都要將添加元素之後的所有元素向後移動。

這麼做有兩個好處：

1. 不用申請新數組。
2. 從後向前填充元素，避免了從前向後填充元素時，每次添加元素都要將添加元素之後的所有元素向後移動的問題。

時間複雜度，空間複雜度均超過100%的用戶。

Solution

class Solution {
public:
    string replaceSpace(string s) {
        int count = 0;
        int sOldSize = s.size();
        for ( int i = 0; i < s.size(); i++ ) {
            if ( s[i] == ' ' ) count++;
        }

        s.resize(s.size() + count * 2 ); // key: 先擴充好新字串的長度
        int sNewSize = s.size();
        for ( int i = sOldSize - 1, j = sNewSize - 1; i >= 0; i--, j-- ) {
            if ( s[i] != ' ' ) s[j] = s[i];
            else {
                s[j] = '0';
                s[j-1] = '2';
                s[j-2] = '%';
                j -= 2;
            }
        }

        return s;
    }
};