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

Question

I came across this interview question and would like to help in trying to understand its solution:

Write a method to replace all spaces in the string with "% 20".

Solution (from the 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 ... First, I would like to understand the algorithm before diving into the code.

Answer 1

This pattern is broken.

Buffer overflow, one pointless line scan (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 replace one character ('') with three characters, we first count the number of spaces to calculate the size increase.

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

This cannot be done as follows: you must allocate more memory , but here we extend the size of the string variable. I believe that it is best to highlight a new variable, as the next step will be easier with another.

 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 step should work if the line is correctly expanded, but you can rewrite it a bit to be clearer.

I suggest something similar, assuming that newstr is our new variable, highlighted in the previous 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 reverse loop (no need to highlight another line with this):

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

Answer 3

the algorithm is this: first count the number of spaces. let's say the string is "ae rt", so that means 2 spaces .. and the current length is 6 (5 in case c, since the index is 0). the output line should be "ae% 20r% 20t". length = 10 (9 in the case of index = 0) so the new length is 6+ '2' * 2, so it reaches 10 ...

this is how the length is adjusted. then he crosses the reverse and places the character in character. When it encounters space, it puts% 20 in the opposite direction, since it crosses the original line in reverse order ...

Answer 4

As I can see, he first searches the string to find all the spaces, and then tries to lengthen the string so that it matches two extra characters (20) per space in the string (but I don't think it allocates space, though), then it again goes through the line, but this time in the reverse order, placing every character that is not space at the back of the new line, and if it encounters space, instead it puts% 20 there, but it does the opposite.

Answer 5

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