面试题4：替换空格

题目：请实现一个函数，把字符串中的每个空格替换成“%20”。例如输入“We are happy.”，则输出“We%20are%20happy.”。

分析

最容易想到的办法就是从前向后扫描字符串，如果遇到空格，就把它后面的子串向后移动2个字节长度。

代码如下

string ReplaceBlank(string str)
{
    int i,j;
    int len=str.size();
    for(i=0;i<len;++i)
    {
        if(str[i]==' ')
        {
            len+=2;
            str.resize(len);
            for(j=len-3;j>i;--j)
            {
                str[j+2]=str[j];
            }
            str[i++]='%';
            str[i++]='2';
            str[i]='0';
        }
    }
}
````

以上代码还可以优化的地方有

1. 先扫描一遍字符串，统计空格个数，然后一次性分配足够的空间

2. 使用memmove代替一个一个地拷贝（具体效率取决于memmove的效率）

   不过，以上代码的时间复杂度为O(n^2)，在面试中写出这样的代码，妥妥的不通过！

   究其原因，时间主要浪费在了每个空格后面子串的拷贝上了。因为没遇到一个空格，我们都要讲它后面的子串拷贝一次。所以可从这个角度着手改进。

   我们可以从后往前拷贝，这样就可以减少拷贝的次数，每个字符至多移动一次就可以完成。思想是：

3. 先扫描一次字符串，统计出空格的个数。然后在尾部分配足够的空间。

4. 设两个指针i和j，i指向当前待拷贝的字符，j指向str[i]应拷贝到的位置。

5. 从后往前拷贝，如果str[i]不为空格，则str[j--]=str[i--]；

6. 否则使i减1，在j及其前面两个字符位置处填充\"%20\"。

   代码如下

   string ReplaceBlank(string str)
   {
       int len=str.size();
       if(len==0)
           return str;
       int BlankCount=0;
       int i=0;
       while(i<len)
       {
           if(str[i++]==' ')
               BlankCount++;
       }
       str.resize(len+BlankCount<<1);
       int j=str.size()-1;
       i--;
       while(i>=0)
       {
           if(str[i]!=' ')
           {
               str[j--]=str[i--];
           }
           else
           {
               str[j--]='0';
               str[j--]='2';
               str[j--]='%';
               i--;
           }
       }
       return str;
   }
   

这个算法的时间复杂度是O(n)，比上一个要好很多。

以上

如果你有任何想法或是可以改进的地方，欢迎和我交流！

完整代码及测试用例在github上：[点我前往]()