6

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.

Improve this question
3
  • Uh, if this is C then it is broken. It does not allocate more memory for the result. Commented Mar 5, 2011 at 10:24
  • true...its trying to resize a static array...but then again..what would be the correct algorithm to solve this question? Commented Mar 5, 2011 at 10:26
  • 3
    I've compiled and tried this; and it works. But it's broken and dangerous since you're stepping on some other memory place's toes. Don't do stuff like this; if you need more place at runtime, you're going to have to use malloc sooner or later. Commented Mar 5, 2011 at 10:28

5 Answers 5

Reset to default
12

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;
}
Improve this answer
Sign up to request clarification or add additional context in comments.

7 Comments

that works...(we need to add dst[dstIndex] ='\0' just before printing the new string though!)
This solution allocate a second char array, it can be done without it keeping the reverse loop and extending the first one correctly.
@Krtek: no it can't, the original str[] does not have enough space for "helo%20b"
@maxpayne: that lacking \0 is what I get for changing calloc to malloc before paste. Edited and fixed :)
@Muggen: No. Original space is counted in the len variable. New "space" needs 2 extra chars. " " would require 1(len) + 1(spaces)*2 + 1(0-term) chars to exactly fit "%20\0"
|
3 
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];
    }
}
Improve this answer

4 Comments

how do i copy the remaining part of the string 3 places further and insert %20 ?
I edited my answer with another solution... But actually I'm thinking that the given code may work if the string is properly extended.
so you're saying that the original code would work provided we dynamically allocate the array and extend it properly?
I didn't test it, but I think it should work. A comment to your question points out in the same direction.
2

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...

Improve this answer

Comments

1

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.

Improve this answer

Comments

1 
/* 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;
}
Improve this answer

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.