【字符串】替换空格

题目描述：

请实现一个函数，将一个字符串中的空格替换成“%20”。例如，当字符串为 We are happy. 则经过替换之后的字符串为 We%20are%20happy. 。注意，输出字符串的长度必须保证和原字符串的长度相等。

思路分析：

遍历字符串中的每个字符，如果不是空格，则将其拷贝到新字符串中；如果是空格，则在新字符串中添加“%20”。由于需要保证输出字符串的长度与原字符串相等，因此需要提前计算出新字符串所需的空间，并将新字符串的长度赋值给原字符串。

代码实现：

C++ 实现代码：

class Solution {

public:

    void replaceSpace(char *str,int length) {

        //计算新字符串所需空间

        int count=0;

        for(int i=0;i<length;++i){

            if(str[i]==' '){

                count++;

            }

        }

        int newLength=length+count*2;

        

        //从后往前复制字符，遇到空格插入“%20”

        for(int i=length-1,j=newLength-1;i>=0;--i){

            if(str[i]==' '){

                str[j--]='0';

                str[j--]='2';

                str[j--]='%';

            }

            else{

                str[j--]=str[i];

            }

        }

        

        //赋值新字符串的长度

        length=newLength;

    }

};

Python 实现代码：

class Solution:

    def replaceSpace(self, s: str) -> str:

        count = 0

        for c in s:

            if c == ' ':

                count += 1

        new_str = [' '] * (len(s) + count * 2)

        i, j = len(s) - 1, len(new_str) - 1

        while i >= 0:

            if s[i] == ' ':

                new_str[j], new_str[j - 1], new_str[j - 2] = '%', '2', '0'

                j -= 3

            else:

                new_str[j] = s[i]

                j -= 1

            i -= 1

        return ''.join(new_str)

时间复杂度分析：

遍历一遍字符串，时间复杂度为 O(n)。

空间复杂度分析：

需要开辟一个新的字符数组存储新字符串，空间复杂度为 O(n)。

总结：

本题思路较为简单，需要注意的点有两个：

计算新字符串所需的空间；

从后往前复制字符，遇到空格插入“%20”。

熟练掌握字符串相关算法，对于程序员而言非常重要。