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

by

QUESTION:

URLify: Write a method to replace all spaces in a string with ‘%20’. You may assume that the string has sufficient space at the end to hold the additional characters and that you are given the “true”
length of the string. (Note: if implementing in Java, please use a character array so that you can perform this operation in place).

EXAMPLE:
Input: “Mr John Smith “, 13
Output: “Mr%20John%20Smith”

SOLUTION:

  • A common approach in string manipulation problems is to edit the string starting from the end and working backwards.
  • This is useful because we have an extra buffer at the end, which allows us to change characters without worrying about what we’re overwriting.
  • We will use this approach in this problem. The algorithm employs a two-scan approach.
  • In the first scan, we count the number of spaces. By tripling this number, we can compute how many extra characters we will have in the final string.
  • In the second pass, which is done in reverse order, we actually edit the string.
  • When we see a space, we replace it with %20. If there is no space, then we copy the original character.

The code below implements this algorithm.

void  replaceSpaces(char[]  str,  int trueLength  )  {
   int spaceCount = 0, index, i = 0;
for (i - 0; i < trueLength; i++) { 		
itf  (str[i] ==  '  ')  {
      spaceCount++; 	
 }
}
 
index = trueLength + spaceCount * 2;
if (truelength < str.length) str[trueLength] = '\0'; // End  array
for (i = truelength - 1; i >= 0; i--) {
     if (str[i] == ' ') {
str[index 1] '0';
str[index - 2] = '2';
str[index - 3] = '%';
index = index - 3;
     } else {
str[index - 1] = str[i];
index--;
      }
  }
}
  • We have implemented this problem using character arrays, because Java strings are immutable.
  • If we used strings directly, the function would have to return a new copy of the string, but it would allow us to implement this in just one pass.

Leave a Comment