题解 | #替换空格#

题目的主要信息：

将一个字符串s中的每个空格替换成“%20”
保证字符串中的字符为大写英文字母、小写英文字母和空格中的一种

方法一：字符串截取相加

具体做法：
我们可以用下标遍历字符串，每次检查下标所在位置的字符是否为空格，如果不是空格，下标继续往后，如果是空格则调用substr函数将字符串从空格前后截断，然后中间添加"%20"后相连即可。
图片说明

class Solution {
public:
    string replaceSpace(string s) {
        int index = 0; //下标
        while(index < s.length()){ //遍历字符串下标
            if(s[index] != ' ') //非空格下标往前走
                index++;
            else{ //空格不连，换成%20
                s = s.substr(0, index) +  "%20" + s.substr(index + 1);
                index += 3; //跳过%20
            }
        }
        return s;
    }
};

复杂度分析：

时间复杂度： $O(n^2)$ ，其中 $n$ 为字符串长度，下标遍历字符串为 $O(n)$ ，循环中最坏情况每次都调用两个substr函数，substr函数复杂度为 $O(n)$
空间复杂度： $O(1)$ ，无额外空间使用

方法二：字符串复制替换

具体做法：
准备一个返回的字符串res，先定为空，遍历所给字符串，遇到非空格直接复制到res中，遇到空格，就将"%20"添加到res中。

class Solution {
public:
    string replaceSpace(string s) {
        string res = "";
        for(int i = 0; i < s.length(); i++){ //遍历字符串
            if(s[i] != ' ') //非空格直接复制
                res += s[i];
            else //空格就替换
                res += "%20"; 
        }
        return res;
    }
};

复杂度分析：

时间复杂度： $O(n)$ ，其中 $n$ 为字符串长度，一次遍历即可
空间复杂度： $O(1)$ ，看起来比方法一额外使用了空间，但是res属于返回函数必要空间，因此还是没有额外使用空间

方法三：Python函数直接替换

具体做法：
Python中replace函数可以直接将字符串中全部的第一个参数子字符串替换成第二个参数子字符串。

class Solution:
    def replaceSpace(self , s ):
        return s.replace(" ", "%20") #调用replace函数

复杂度分析：

时间复杂度： $O(n)$ ，replace函数时间复杂度为 $O(n)$
空间复杂度： $O(1)$ ，无额外空间使用