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

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.

---

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;
}

---

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];
    }
}

---

the algorithm is this way : first count the number of spaces.. say the string is "ae r t" so that means 2 spaces.. and current length is 6 (5 in case of c as index is 0) .. the output string should be "ae%20r%20t" .. length = 10 ( 9 in case of index =0) so the new length is 6+ '2'*2 so her it comes to 10 ...

this how length is adjusted .. then he traverses from reverse and places character by character.. when ever he encounters space he places %20 in reverse since he traversing the original string in reverse order...

---

As I see it, it first searches through the string to find all the spaces, then it tries to lengthen the string to fit the 2 extra characters (20) per space in the string (but I don't think he allocates the space though), then it goes through the string again, but this time in reverse, placing each character that is not a space in the back of the new string and if it encounters a space it places %20 in there instead, but it does so in reverse.

---

/* program to replace the space with "%20" */
/* Author senthilkumar M */

eg str = "ab cd ef"
   str1 = "ab%20cd%20ef"


char *space_replace(char *str)
{
        int l = strlen(str);
        int i = 0, j =0;
        int spc = 0, nl = 0;
        char *str1 = NULL;

        for(i = 0; i < l; i++)  {
                if(str[i] == ' ') {
                        spc++;
                }
        }
        nl = l + 2*spc + 1;
        str1 = (char *) malloc(sizeof(char) * nl);
        if(!str1) {
                fprintf(stdout, "malloc failed \n");
                return NULL;
        }
        for(i = 0; i < l; i++) {
                if(str[i] == ' ') {
                        str1[j++] = '%';
                        str1[j++] = '2';
                        str1[j++] = '0';
                } else {`enter code here`
                        str1[j++] =  str[i];
                }
        }
        str1[j] = '\0';
        return str1;
}