Wednesday, May 15, 2013

Replacing spaces in a character array with %20

Given a character array which contains some spaces. we have to replace all the spaces with the string '%20'. This algorithm is commonly used during HTML encoding of the URLs in the web browsers. Assume that the array has enough space at the end to accommodate the expanded string, how do we do this efficiently?

The following solution uses no extra space and runs in O(n) time. The trick here is to start copying the characters from the end, and wherever we find space replace it with '%20'. The following C++ code does exactly that.



#include <iostream>
#define MAX 100
using namespace std;

void replaceSpace(char *array)
{
 int len=0,i;
 int spaceCount = 0;
 //this loop calculates the spaces and length of the string
 for( i = 0 ; array[i] != '\0' ; i++ )
 {
  //count spaces
  if( array[i] == ' ')
   spaceCount++;
  //update length
  len++;
 }
 //array has enough space, try to copy the string from end
 //end index will be length + 2*no of spaces bcoz for each space
 //there will be (3-1=2) two additional characters inserted
 int resInd = len + 2*spaceCount;
 
 //len is the index of '\0' (i.e last) in the original string
 //start copying from there
 while ( len >= 0)
 {
  //if space, insert %20 in reverse, bcoz we are copying from reverse
  if( array[len] == ' ')
  {
   array[resInd--] = '0';
   array[resInd--] = '2';
   array[resInd--] = '%';  
  }
  else //copy as it is
  {
   array[resInd--] = array[len];
  }
  len--; 
 }
}
int main()
{
 char chArray[MAX];
 gets(chArray);
 replaceSpace(chArray);
 cout<<chArray<<endl;
 return 0;
}