I have been working my way through the exercises in the book Cracking the Coding Interview. I wanted to get feedback for the following exercise.
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.
Example:
Input: "Mr_John_Smith____ ", 13
Output: "Mr%20John%20Smith"Note: I am using '_' to represent spaces above because I could not get spaces to format nicely.
I would be interested in feedback on my code and time/space complexity computation below, and would also be interested to know if there is any way to improve the time or space complexity of my code.
def urlify(in_string, in_string_length):
in_string = list(in_string)
for position, character in reversed(list(enumerate(in_string[0:in_string_length]))):
if character == ' ':
in_string[position + 3:in_string_length + 2] = in_string[position + 1:in_string_length]
in_string[position:position + 3] = '%20'
in_string_length += 2
return ''.join(in_string)
My guess is that the time complexity of the code above is \$O(1(n - s) +sn)\$ where \$n\$ is the length of the input string, \$ s\$ is the number of spaces in the input string (not including trailing spaces).
My reasoning is that if there are 0 spaces then the for loop will only do constant work checking the if statement and then perform the join at the end which all together is \$O(n)\$ whereas in the other extreme case where there are \$n\$ spaces, the work done will be \$O(n^{2})\$. Lastly I think the space complexity is \$O(n).\$
