题解 | #替换空格#

解题思路1：从后往前来对有空格的地方插入'%20',首先查看字符串中空格出现的次数，然后对字符串进行扩容（在原字符串长度的基础上添加空格数✖2的长度），然后按照下面的操作来进行。(1)p1指向原来字符串的末尾，p2指向扩容之后字符串的末尾，即新字符串的末尾；(2)从p1开始，将对应位置的字符复制给p2，然后p1--，p2--直到遇到空格；(3)当遇到空格时，在p2位置依次插入'0','2','%'（因为我们是从后往前复制的），此时p2的位置向前移动了三位，不要忘记p1--;(4)当p1=0并且p1>p2时,结束循环，输出新的字符串。

时间复杂度：O(n)，所有的字符串只复制了一次；

空间复杂度：O(1)

下面是基于C++实现的：

class Solution {
public:
    string replaceSpace(string s) {
        //如果是空字符串的情况
        if(s.empty()){
            return s;
        }
        
        int num_blank = 0;
        int i = 0;
        //计算空格的个数
        while(i < s.length()){
            if(s[i] == ' '){
                num_blank += 1;
            }
            i += 1;
        }
        //计算扩展之后的长度
        int new_length = s.length() + num_blank*2;
        //p1,p2分别指向原字符串的末尾和扩展之后新字符串的末尾
        int p1 = s.length();
        int p2 = new_length;
        //对原字符串进行扩容
        s.resize(new_length);
        //判断条件，p1要大于零，并且小于p2
        while(p1 >= 0 && p1 < p2){
            //如果原字符串出现空格，则添加%20，p2向前移动三位
            if(s[p1] == ' '){
                s[p2--] = '0';
                s[p2--] = '2';
                s[p2--] = '%';
            }else{
                //如果没有出现空格，就直接赋值，p2向前移动一位
                s[p2--] = s[p1];
            }
            //不管是不是空格，p1每次向前移动一位，p1的内容控制p2的移动次数
            --p1;
        }
        return s;
    }
};

解题思路2：使用栈，遇到空格就将'%20'入栈，不是空格就直接入栈，然后以字符串的形式返回即可。

时间复杂度：O(n)

空间复杂度：O(n)

下面是基于python实现的：

class Solution:
    def replaceSpace(self , s: str) -> str:
        stack = []
        for c in s:
            # 如果是空格，'%20'入栈
            if c == ' ':
                stack.append('%20')
            else:
                # 不是空格正常入栈
                stack.append(c)
        # 以字符串形式返回
        return ''.join(stack)

总结：在数组中需要复制移动数字的时候，也可以考虑从后往前复制，这样可以减少移动的次数，从而提高效率。