剑指 Offer 05. 替换空格

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

方法1：由前向后遍历（时间复杂度为O(n^2)）

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param s string字符串 
     * @return string字符串
     */
    string replaceSpace(string s) {
        // write code here
        string new_str;
	    for(int i=0;i<s.length();i++)
	    {
	    	if(s[i]==' ')
		    {
			    new_str.push_back('%');
			    new_str.push_back('2');
			    new_str.push_back('0');
		    }	
		    else
		    {
			    new_str.push_back(s[i]);
		    }
	    } 
	    return new_str;
    }
};

方法2：由后往前遍历（时间复杂度为O(n)）

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param s string字符串 
     * @return string字符串
     */
    string replaceSpace(string s) {
        // write code here
        int len=s.length();
	    int num=0,point=len;
	    for(int i=0;i<len;i++)
	    {
		    if(s[i]==' ')
		    {
			    num++;
			    s+="00"; //给字符串添加2位字符位
		    }
	    }
	    point=len+2*num;
	    for(int i=len-1;i>=0;i--)
	    {
		    if(s[i]==' ')
		    {
			    s[point-1]='0';
			    s[point-2]='2';
			    s[point-3]='%';
			    point-=3;
		    }
		    else
		    {
		    	s[point-1]=s[i];
			    point-=1;
		    }
			
	    }
	    return s;
    }
};