题目描述

请实现一个函数，把字符串中的每个空格替换成”%20”。

你可以假定输入字符串的长度最大是1000。
注意输出字符串的长度可能大于1000。

样例

输入："We are happy."

输出："We%20are%20happy."

C++ 代码

/*
思路：
    1. 统计替换后字符串的长度
    2. 在原字符串末尾和新字符串末尾和设置两个指针p和q, 进行逆序遍历
    3. 当在p原字符串中遍历到空格时，新字符串q对应位置依次填充0 2 % ，向前移动3个；否则单纯p指针处字符，填充到q指针处。
    4. 当p和q指同一位置时，循环结束。

需要注意的一点：
    计算好新字符串长度后，要为str重新设置大小，否则会出现越界问题。

空间复杂度：O(1)
时间复杂度：O(n)
*/


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

        //统计新字符串的长度
        int count = 0;
        for(int i=0; i<str.length(); i++)
            if(str[i] == ' ')
                count++;

        //长度没变，没有空格，返回原字符串
        if(count == 0)
            return str;            

        int new_length = str.length() + 2 * count;
        int ori_length = str.length() ;

        //重新设置大小
        str.resize(new_length);

        while(ori_length != new_length)
        {
            if(str[ori_length] == ' ')
            {
                str[new_length--] = '0';
                str[new_length--] = '2';
                str[new_length--] = '%';
            }
            else
                str[new_length--] = str[ori_length];
            ori_length--;
        }
        return str;

    }
};