首页 > 代码库 > 字符串替换空格

字符串替换空格

题目:请实现一个函数,把字符串中的每个空格替换成"%20",并尽可能的降低时间复杂度。例如:输入"We are happy.",则输出"We%20are%20happy."

分析:最直接的做法就是从头到尾扫描字符串,每一次碰到空格字符的时候就做替换。但是这样是把一个字符替换成3个字符,我们必须要把空格后面的所有的字符都后移两个字节,否则就会有两个字符别覆盖,其时间复杂度为O(n2)

            我们可以先遍历一次字符串,统计出字符串中空格的总数,从而计算出替换后字符串的总长度。然后我们从字符串的尾部进行复制替换。设置两个指针P1,P2,P1指向原字符串长度的结尾,P2指向替换后字符串的结尾,然后向前移动P1,逐个P1所指的复制到P2,当遇到空格时,将P1向前移动一格,然后在P2之前插入"%20",然后将P2前移三个字符串,然后继续前进,最终完成。这种算法的时间复杂度是O(n),其C++代码如下:


void ReplaceBlank(cahr string[].int length)
{
    if(string==NULL||length<=0)
        return;
    
    int originalLength=0;
    int numberOfBlank=0;
    int i=0;
    while(string[i]!=‘\0‘)
    {
        ++originalLength;
        if(string[i]==‘ ‘)
            ++numberOfBlank;
        ++i;
    }
    
    int newLength=originalLength+numberOfBlank*2;
    if(newLength>length)
        return;
    
    int indexOfOriginal=originalLength;
    int indexOfNew=newLength;
    while(indexOfOriginal>=0&&indexOfNew>indexOfOriginal)
    {
        if(string[indexOfOriginal]==‘ ‘)
        {
            string[indexOfNew--]==‘0‘;
            string[indexOfNew--]==‘2‘;
            string[indexOfNew--]==‘%‘;
         }
         else
         {
             string[indexOfNew--]=string[indexOfOriginnal];
          }
          indexOfOriginnal;
      }
  }


本文出自 “仙路千叠惊尘梦” 博客,请务必保留此出处http://secondscript.blog.51cto.com/9370042/1581314

字符串替换空格