简单的字符串替换也要好好思考

问题描述：

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

在处理一些网页时，这种替换很有用处，看到题目的第一想法当然就是遍历一遍，遇到空格的话就替换成%20，后面的字符串则整体向后平移。
但仔细思考一下发现如果这么做的话，时间复杂度其实是o(n^{2)。因为大体上每个字符都会平移多次。这时就要想想怎么样让字符串平移的次数只有一次。答案很简单，从后向前遍历即可。时间复杂度从O(n}2)变为O(n)。效率大大增强。C语言代码如下：

#include <stdio.h>
#include <stdlib.h>
#define max 10000
#include <string.h>

void replace(char c[]){
    int len = strlen(c),i,j,n=0;
    for(i = 0; i < len; i++){
        if(c[i] == 32){
            n++;
        }
    }
    int p1 = len - 1;
    int p2 = p1 + 2 * n;
    for(i = p1; i >=0 ; i--){
        if(c[i] == 32){
            c[p2--] = '0';
            c[p2--] = '2';
            c[p2--] = '%';
        }
        else{
            c[p2--] = c[i];
        }
    }
    printf("%s",c);
}
int main()
{
    char origin[max];
    gets(origin);
    replace(origin);
    return 0;
}