Archive

Archive for June, 2011

Reverse a string (or list) in place

June 29, 2011 7 comments

Exercise
Take a string and reverse it in place, i.e. you are not allowed to use another string to store the result. The question concerns the algorithmic part.

Solution
Well, this problem cannot be solved in Python because strings are immutable, i.e. once you create a string, you cannot change it:

>>> s = 'test'
>>> s[0]
't'
>>> s[0] = 'T'
Traceback (most recent call last):
  File "", line 1, in
TypeError: 'str' object does not support item assignment

Note that you would have a similar problem in Java too. However, in C you could change a string in place, but in C a string is actually an array of characters.

To solve this problem in Python, we need to work with an array of characters instead. So, let’s convert a string to a list of characters:

>>> a = 'Jabba Laci'
>>> li = []
>>> li.extend(a)
>>> li
['J', 'a', 'b', 'b', 'a', ' ', 'L', 'a', 'c', 'i']

Now let’s reverse the list in place:

>>> size = len(li)
>>> for i in range(0, size/2):
...     li[i], li[size-1-i] = li[size-1-i], li[i]
...
>>> li
['i', 'c', 'a', 'L', ' ', 'a', 'b', 'b', 'a', 'J']
>>> ''.join(li)
'icaL abbaJ'

Related post

See this problem @reddit.