Saturday, January 18, 2014

Replace all spaces in a string with “%20″ in c-style string

This updated information has been further expanded upon on my new website. You can find the updated details here: https://k5kc.com/cs/algorithms/replace-all-spaces-in-c-style-string-with-20-/.

Problem

Write a C program that will replace all spaces with ‘%20′

Example
Input:              "Mr John Smith    "
Output:            "Mr%20John%20Smith

Solution

The algorithm is as follows:
  1. Count the number of spaces during the first scan of the string.
  2. Parse the string again from the end and for each character:
             If a space is encountered, store “%20”.
             Else, store the character as it is in the newly shifted location.
Java code
public static void ReplaceFun(char[] str, int length) {
    int spaceCount = 0, newLength, i = 0;
         
    for (i = 0; i < length; i++)
    {
        if (str[i] == ‘ ‘)
        {
            spaceCount++;
        }
    }
         
    newLength = length + spaceCount * 2;
    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;
        }
    }
}


Time Complexity: O(N), N is length of the string.

C code
Here is a c code doing the similar stuff, borrowed from here :
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;
}

Point to note here is that when you are using malloc, set the last index to '\0' as it is a c-style string OR you can use calloc.

0 comments:

Post a Comment