字符串替换空格

题目描述

请实现一个函数，将一个字符串中的空格替换成“%20”。例如，当字符串为We Are Happy.则经过替换之后的字符串为We%20Are%20Happy。

注意

原来一个空格字符，替换之后，变成‘%’，‘2’，‘0’三个字符，字符串长度会变长。如果是在原来的字符串上做替换，要保证原来的字符串有足够的空余内存。

从前向后，时间复杂度为O(n^2)

从头到尾扫描字符串，每次碰到空格字符时做替换，空格后所有的字符向后移2个字节。

从后向前，时间复杂度O(n)

先遍历一遍字符串，求出所有空格的总数和字符串实际长度。计算出替换之后的字符串的总长度，从字符串最后开始复制和替换，包括‘\0’。

class Solution {
public:
    void replaceSpace(char *str, int length) {
        if (str == NULL || length <= 0)
            return;

        int blanksize = 0;  //空格数
        int len=0;          //数组实际长度
        for (int i = 0; str[i]!='\0'; i++)//注意此处判断条件不是i<length
        {
            len++;
            if (str[i] == ' ')
                blanksize++;
        }

        int newLen = len + blanksize * 2;
        if (newLen > length)
            return;
        int j = newLen;
        for (int i = len; i >= 0; i--)
        {
            if (str[i] != ' ')
                str[j--] = str[i];
            else
            {
                str[j--] = '0';
                str[j--] = '2';
                str[j--] = '%';
            }
        }
    }
};