面试题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
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
以上代码还可以优化的地方有
1. 先扫描一遍字符串,统计空格个数,然后一次性分配足够的空间
2. 使用memmove代替一个一个地拷贝(具体效率取决于memmove的效率)
不过,以上代码的时间复杂度为O(n^2),在面试中写出这样的代码,妥妥的不通过!
究其原因,时间主要浪费在了每个空格后面子串的拷贝上了。因为没遇到一个空格,我们都要讲它后面的子串拷贝一次。所以可从这个角度着手改进。
我们可以从后往前拷贝,这样就可以减少拷贝的次数,每个字符至多移动一次就可以完成。思想是:
1. 先扫描一次字符串,统计出空格的个数。然后在尾部分配足够的空间。
2. 设两个指针i和j,i指向当前待拷贝的字符,j指向str[i]应拷贝到的位置。
3. 从后往前拷贝,如果str[i]不为空格,则str[j--]=str[i--];
4. 否则使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上:[点我前往]()