I recently wrote a function that replaces every white space with '%20', just for fun (and sharping my coding skills). The input string is terminated with extra white spaces, with the length that the string should have after encoding takes place. For example:
input = "Not encoded " //2 white spaces in the end
output = "Not%20encoded"
Although I was able to implement such encoding in-place, I was still not pleased with the result, specially due to the inner loop that shifts the whole string to the right everytime a white space is found. Here is my solution, written in C#:
public string encode(string str)
{
var array = str.ToCharArray();
for (int i = 0; i < array.Length; i++) {
if (array[i] != ' ') continue;
//switch every char >> 2, from the end of the string to i
for (int j = array.Length - 1; j > i; j--) {
array[j] = array[j - 2];
}
array[i++] = '%';
array[i++] = '2';
array[i] = '0';
}
return new String(array);
}
I'm looking for a solution that operates in O(n), possibly performing a single traversal on the input string. Additional feedback on how to improve performance/readability of my function are always very appreciated :)