URLIfy a character array using Python - follow-up

Question

This is a follow up to my last code review:

URLify a string using Python

This problem has been reviewed in other languages, but I tried to solve this without looking at those answers.

I am hoping that I achieved \$O(n)\$ time and \$O(1)\$ space as was explained in my last review. I would also appreciate any tips on improving clarity and/or making the code more pythonic without sacrificing time/space complexity.

def count_spaces(in_char_array):
   num_spaces = sum(1 for char in in_char_array if char == ' ')
   return  num_spaces

def urlify(in_char_array, true_length):
   num_spaces = count_spaces(in_char_array[:true_length])
   urlified_length = true_length + 2*num_spaces

   urlified_pos = urlified_length - 1
   for in_char in reversed(in_char_array[:true_length]):
       if in_char == ' ':
           in_char_array[urlified_pos-2:urlified_pos+1] = '%20'
           urlified_pos -= 3
       else:
           in_char_array[urlified_pos] = in_char
           urlified_pos -= 1
    return in_char_array

I tested this as follows -

urlified_string = urlify(list('Mr John Smith    '), 13)

print(urlified_string)
print(''.join(urlified_string))

The output was:

['M', 'r', '%', '2', '0', 'J', 'o', 'h', 'n', '%', '2', '0', 'S', 'm', 'i', 't', 'h']

Mr%20John%20Smith

Answer 1

\$O(n)\$ time with \$O(1)\$ space is a hard, and somewhat extreme requirement. Sure the \$O(n)\$ can be achieved easily. But the \$O(1)\$ is not.

Using lists, to achieve \$O(1)\$ means you have to change the list in-place. This means any slicing or helper methods are instantly not an option. This was pointed out by 200_success. Take:

>>> a = 'abc  '
>>> id(a)
51272544
>>> id(a.strip())
48713152
>>> id(a[:-2])
44833440
>>> del a[-2:]
TypeError: 'str' object does not support item deletion
>>> a = list('abc  ')
>>> id(a)
51232040
>>> id(a.strip())
AttributeError: 'list' object has no attribute 'strip'
>>> id(a[:-2])
51246424
>>> del a[-2:]
>>> a
['a', 'b', 'c']
>>> id(a)
51232040

So to achieve the requirements you need is hard. And I'd say unreasonable in the real world.

I also agree with Phrancis that your functions input is bad. To achieve what you want, we'd want to manually implement strip. And we're only allowed to make in place changes to the array. This means the function will be, using type hints, inplace_strip(data: list).

Since strip removes just spaces at the front and back of the list, it's easy to implement efficiently. Just count the amount of places to remove from the front and back, and then delete them.

def inplace_strip(data: list):
    for i in range(len(data)):
        if data[i] != ' ':
            break
    else:
        del data[:]
        return None
    if i:
        del data[:i]

    for i in range(len(data)-1, -1, -1):
        if data[i] != ' ':
            break
    if i != len(data):
        del data[i+1:]

Is this still \$O(n)\$ time? Yes. If we look at the time complexity of the list operations I used, then we should see that they are all \$O(n)\$ or smaller. And so the function is \$O(n)\$.

After this we need to mutate the list so that we can change all ' ' to '%20'. There are three ways we can do this:

• Set Item, changes the return to ['a', 'b', '%20', 'c'].
• Set Slice, has the time complexity of \$O(k+n)\$.
• Generator, you're going to change the space complexity outside of this function to \$O(n)\$.

So it's really a hard choice.
I'd use a generator as the function 'has no problems', it's you who's changing the space complexity to \$O(n)\$. And so when ever you get a ' ' you'll yield the '%20'. But you'll split it up so that there's three yields.

This makes the function simply:

def urlify(data: list):
    inplace_strip(data)
    for char in data:
        if char == ' ':
            yield '%'
            yield '2'
            yield '0'
        else:
            yield char

A function which will always have the usage as, ''.join(urlify(data)). And so wastes all that hard work. Instead I'd say to use str.strip and str.translate, this makes the code much simpler, which allows you to change the function to:

def urlify(data: list):
    return data.strip().translate({ord(' '): '%20'})

Answer 2

Since you are using Python 3.x you could take advantage of the new type hints. According to PEP 484:

This PEP aims to provide a standard syntax for type annotations, opening up Python code to easier static analysis and refactoring, potential runtime type checking, and (perhaps, in some contexts) code generation utilizing type information.

Of these goals, static analysis is the most important. This includes support for off-line type checkers such as mypy, as well as providing a standard notation that can be used by IDEs for code completion and refactoring.

Even if you don't use static code analysis at the moment, type hints still have the advantage of making the code easier to read and understand.

---

The count_spaces function could return directly from the list comprehension expression (type hints added).

The addition of the in_ prefix to the function parameters really doesn't add much value, as function parameters are always a form of input by definition. Since Python does not really use the term "array", calling it a list more be more appropriate.

def count_spaces(char_list: list) -> int:
    return sum(1 for char in char_list if char == ' ')

Answer 3

>>> in_char_array = list('Mr John Smith    ')
>>> in_char_array
['M', 'r', ' ', 'J', 'o', 'h', 'n', ' ', 'S', 'm', 'i', 't', 'h', ' ', ' ', ' ', ' ']
>>> true_char_array = in_char_array[:13]
>>> true_char_array[2] = '.'
>>> true_char_array
['M', 'r', '.', 'J', 'o', 'h', 'n', ' ', 'S', 'm', 'i', 't', 'h']
>>> in_char_array
['M', 'r', ' ', 'J', 'o', 'h', 'n', ' ', 'S', 'm', 'i', 't', 'h', ' ', ' ', ' ', ' ']

Draw your own conclusions about how much space is being used in your solution. =)