问题抽象

替换字符串中的空格为”%20”

算法1 拷贝替换

直接将原字符串拷贝到新的字符串中，顺便做替换

复杂度

时间：$O(N)$
空间: $O(N)$

代码

class Solution {
public:
    string replaceSpace(string s) {
        string ans;
        for(auto ch : s){
            if(ch == ' '){
                ans += "%20";
            }else{
                ans += ch;
            }
        }
        return ans;
    }
};

算法2 扩容替换（双指针）

难点在于想到扩容，以及扩容后在原字符串上操作不会覆盖、顺序正确

关键点在于想到扩容后长度一定正确，而我们只要开两个指针，分别指向原字符串末尾和扩容字符串末尾，同步递减（替换处除外），就必定能保证顺序正确

复杂度

时间：$O(N)$
空间：$O(N)$, 最坏情况是全空格

代码

class Solution {
public:
    string replaceSpaces(string &str) {

        int len = 0;
        for (auto c : str)
            if (c == ' ')
                len += 3;
            else
                len ++ ;

        int i = str.size() - 1, j = len - 1;

        str.resize(len);

        while (i >= 0)
        {
            if (str[i] == ' ')
            {
                str[j -- ] = '0';
                str[j -- ] = '2';
                str[j -- ] = '%';
            }
            else str[j -- ] = str[i];
            i -- ;
        }
        return str;
    }
};