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] != ' ' ; 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 ' ' (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;
}