1.4 - Write a method to replace all spaces in a string with "%20". You may assume that the string has sufficient space at the end of the string 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 "
Output: "Mr%20John%20Smith"
This problem was pretty straightforward, and I'd like to alter it a bit. I am not going to assume that the string has enough spaces at the end, because somewhere down the line, some engineer will not read the documentation and toss in a string with no trailing spaces. Since I assumed that there were trailing spaces, that's a nice crash that was unanticipated. Instead, my method will trim any space characters that are leading or trailing the string. That way, we are sure that every string that is passed to this method DOES NOT have enough space to store the extra characters. Every string is passed through the Trim() method to be equal. We can avoid having to throw an exception when we have some strings with trailing spaces and some strings without.
The original problem was also pretty clear that in-place operations are preferred. I wrote my method in C#. This means that the strings are immutable, and I cannot swap characters in place. Instead, I tried to do the next best thing. Convert the string to a character array, swap the characters in place in that array, then convert the array back into a string. I understand that new memory is allocated for the character array, and then memory is allocated again for the new string, so the method isn't quite as in-place as it would be in Java, but that's OK for the exercise.
The first thing I do (after the Trim()) is to count the number of spaces in the string. For each space, we need two more empty characters added to the string to make sure there is enough room to store all the "%20"'s. After that is done, we convert the string to a character array.
From here, we begin moving characters from the end of the original string to the end of the lengthened string. For all non-space characters, it's a simple move. When we get to a space character, we replace it with "%20". In either case, we decrement our indices carefully until we get to the beginning of the string. From here, we cast the array back into a string and store it as the original variable, which is passed back to the caller as it was given as reference.
My goal for this method was not the shortest code, but the shortest time complexity. The time complexity is O(n), which means it will scale well when given large strings. Somehow, I have a feeling somebody will try to pass in a string that contains the entire manuscript of "War and Peace" so that they have an HTML version whenever they feel the need to read the classic...
Here is the code:
//Brandon Theolet
//
//1.4 Write a method to replace all spaces in a string with '%20'. If implementing in Java, please use a character array so that you can perform this operation in place (McDowell, 2012).
//
//McDowell, G. L. (2012). Cracking the coding interview: 150 programming questions and solutions. Palo Alto, CA: Career Cup, LLC.
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace Problem1_4
{
class Program
{
static void Main(string[] args)
{
//Get a string from the user.
string myString;
Console.Clear();
Console.Out.Write("Please enter a string: ");
myString = Console.In.ReadLine();
//Call the method and display a before and after
//comparison showing the transformation.
Console.Clear();
Console.Out.WriteLine("Given string:\t\t\"" + myString + "\"");
insertHTMLSpaces(ref myString);
Console.Out.WriteLine("\nTransformed string:\t\"" + myString + "\"\n");
//Pause to display results before closing.
Console.Out.Write("Please press any key to exit...");
Console.ReadKey();
}
static void insertHTMLSpaces(ref string myString)
{
//The original problem has been modifed for
//this exercise. It stated that we can assume
//there is enough space at the end of the
//string to insert the characters. Instead,
//we are not assuming there are enough spaces
//to do the in-place operations. This means we
//have to create the space first. For every
//space present in the string, we need to add
//two more.
//If extra spaces were given at the beginning or end, remove them.
myString = myString.Trim();
//The true length of the string.
int stringLength = myString.Length;
if (stringLength < 1) return;
for (int myIndex = 0; myIndex < stringLength; myIndex++)
{
//Add additional spaces for in-place operations.
if (myString[myIndex] == ' ') myString += " ";
}
//The last character index in the lengthened string.
int lastCharIndex = myString.Length - 1;
//The last character from the original string.
int partitionIndex = stringLength - 1;
//Convert the string to a char array for in-place swaps.
char[] myCharArray = myString.ToCharArray();
while (partitionIndex >= 0)
{
if (myString[partitionIndex] != ' ')
{
//Character at partitionIndex is not a space.
//Move it to the rear of the string.
myCharArray[lastCharIndex] = myCharArray[partitionIndex];
lastCharIndex--;
partitionIndex--;
}
else
{
//Char at partitionIndex is a space. Replace
//it as neccessary.
myCharArray[lastCharIndex] = '0';
myCharArray[--lastCharIndex] = '2';
myCharArray[--lastCharIndex] = '%';
lastCharIndex--;
partitionIndex--;
}
}
//Allocate the transformed string back to the original
//variable since it was passed by reference.
myString = new string(myCharArray);
//O(n) time complexity, in-place swaps in the char array,
//method ensures there is enough memory to insert extra
//characters. Return control to caller.
return;
}
}
}
Reference:
McDowell, G. L. (2012). Cracking the coding interview: 150 programming questions and solutions. Palo Alto, CA: Career Cup, LLC.
