Write a method to replace all spaces in a C style string

Question

I've encountered this interview question and would like some help in trying to understand its solution:

Write a method to replace all spaces in a string with ‘%20’.

Solution (from a forum) :

char str[]="helo b";
int length = strlen(str);
int spaceCount = 0, newLength, i = 0;

for (i = 0; i < length; i++) {
if (str[i] == ' ') {
    spaceCount++; //count spaces...
}
}

newLength = length + spaceCount * 2;   //need space for 2 more characters..
str[newLength] = '\0';

for (i = length - 1; i >= 0; i--) {
    if(str[i] == ' ') {
        str[newLength - 1] = '0'; //???
        str[newLength - 2] = '2';
        str[newLength - 3] = '%';
        newLength = newLength - 3;
    } else {
        str[newLength - 1] = str[i];
        newLength = newLength - 1;
    }
}

This program does not work for me...i would first like to understand the algorithm before diving into the code.

Answer 1

That sample is broken.

Buffer overflow, One pointless scan of the string (strlen), Hard to read.

int main() {
  char src[] = "helo b";
  int len = 0, spaces = 0;
  /* Scan through src counting spaces and length at the same time */
  while (src[len]) {
    if (src[len] == ' ')
      ++spaces;
    ++len;
  }
  /* Figure out how much space the new string needs (including 0-term) and allocate it */
  int newLen = len + spaces*2 + 1;
  char * dst = malloc(newLen);
  /* Scan through src and either copy chars or insert %20 in dst */
  int srcIndex=0,dstIndex=0;
  while (src[srcIndex]) {
    if (src[srcIndex] == ' ') {
      dst[dstIndex++]='%';
      dst[dstIndex++]='2';
      dst[dstIndex++]='0';
      ++srcIndex;
    } else {
      dst[dstIndex++] = src[srcIndex++];
    }
  }
  dst[dstIndex] = '\0';
  /* Print the result */
  printf("New string: '%s'\n", dst);
  /* And clean up */
  free(dst);
  return 0;
}

Answer 2

for (i = 0; i < length; i++) {
    if (str[i] == ' ') {
        spaceCount++; //count spaces...
    }
}

Since we're replacing a single character (' ') with three characters, we first count the number of space in order to compute the size increase.

newLength = length + spaceCount * 2;   //need space for 2 more characters..
str[newLength] = '\0';

This can't be done like this, you must allocate more memory, but here we extends the size of the string variable. I think the best is to allocate a new variable, since the next step will be easier with another one.

for (i = length - 1; i >= 0; i--) {
    if(str[i] == ' ') {
        str[newLength - 1] = '0'; //???
        str[newLength - 2] = '2';
        str[newLength - 3] = '%';
        newLength = newLength - 3;
    } else {
        str[newLength - 1] = str[i];
        newLength = newLength - 1;
    }
}

Finally, this is step should work if the string is properly extended, but it can be a little bit rewritten to be clearer.

I suggest something like this, assuming newstr is our new variable allocated in the precedent step :

int j = 0;
for(i = 0; i < length; i++, j++) {
   if(str[i] == ' ') {
      newstr[j] = '%';
      newstr[++j] = '2';
      newstr[++j] = '0';
   } else {
      newstr[j] = str[i];
   }
}

Or, if you want to keep the backward loop (no need to allocate another string with this one) :

for (i = length - 1, j = newLength - 1; i >= 0; i--, j--) {
    if(str[i] == ' ') {
        str[j] = '0';
        str[--j] = '2';
        str[--j] = '%';
    } else {
        str[j] = str[i];
    }
}