URLify a string using Python

Question

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).\$

Answer 1

Your complexity analyses look correct to me. I would just say, in short, that this function works in O(n²) time.

Note that this is an awkward exercise to do in Python, or any language in which strings are immutable. Since you can't perform the substitutions in place, you have to return a copy, which means that the minimum space requirement is O(n). In that case, you might as well do either:

def urlify(in_string, in_string_length):
    return in_string[:in_string_length].replace(' ', '%20')

… or:

def urlify(in_string, in_string_length):
    return ''.join('%20' if c == ' ' else c for c in in_string[:in_string_length])

… which should also be O(n) space, O(n) time, and much simpler to implement!

That said, if we were to reinterpret the exercise to work on a buffer in place, I think that a better approach would be to make one pass to count the spaces in the input, to figure out the length of the output. Then, copy characters to construct the result, working backwards from the end. That algorithm should take O(n) time and O(1) space.

In summary, depending on how you interpret the exercise, the solution should either be simpler or faster than what you wrote.

Answer 2

I believe this is the simplest way to do this in python:

def urlify(in_string):
    return "%20".join(in_string.split())

Note: There is no need for the length arg if you use this shortcut

Logic: String.split() splits a string to an array of strings, using the provided argument as the delimiter (space by default). "%20".join(array) appends together all elements of an array with "%20" in between each of them.

However, this is obviously not the kind of answer that Gayle (author of CtCI) is looking for. She wants you to modify an array in place. You did that well in most of your code but there were times where you took some shortcuts (assignments to substrings of the list instead of individual 'array' elements). Something like this is a bit closer, as it treats the python list as if it was an array. I think the call to the join function is acceptable and should not be considered too high-level to use because every language has some way to turn a character array into a string (they are basically the same thing).

def urlify(string,length):
    charArr = list(string)
    j = len(charArr)-1
    for i in range(length-1,-1,-1):
        if(charArr[i]!=' '):
            charArr[j] = charArr[i]
            j-=1
        else:
            charArr[j] = '0'
            charArr[j-1] = '2'
            charArr[j-2] = '%'
            j-=3
    return "".join(charArr)

Logic: Traverse backwards from the last letter (not space) of your 'array'. Whenever you hit a letter, move it to the last space in the array. If a space is found, there will now be enough space to add "%20." Do it one character at a time, and continue the loop until you reach index 0.

Time and Space Complexity: Both O(n).