Home > python > Reverse a string (or list) in place

Reverse a string (or list) in place

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.

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]
>>> 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.

  1. Dan
    January 2, 2013 at 14:28

    Could be made a bit more pythonic

    >>> li = list(‘Jabba Laci’)
    >>> for i in range(len(li)/2):
    . . . li[i], li[-i-1] = li[-i-1], li[i]
    >>> ”.join(li)
    ‘icaL abbaJ’

    • January 2, 2013 at 14:31

      True, thanks. I figured out recently that a string can be passed to the constructor of a list.

  2. February 22, 2013 at 17:46

    Or you could write:

    print ‘Jabba Laci'[::-1]

    • February 22, 2013 at 17:49

      Yes, that’s the trivial way. But [::-1] makes a copy of the string, which is not allowed this time in this exercise.

  3. March 21, 2013 at 09:54

    Hi, what are your thoughts on this method:

        s = 'test'
        length, index = len(s), 0
        while index < length:
            s += s[(length - 1) - index]
            index += 1
        s = s[length:]

    Not particularly elegant, AND I have a sneaky feeling I am breaking the rules here. My thinking is that I am not creating a 'copy' of s, but I am effectively de-referencing the pointer (s) and pointing to a new memory block at each iteration. If this is true, then it is REALLLLY memory expensive.

    What are your thoughts?

    • March 21, 2013 at 11:16

      In Python, strings are immutable objects, which means that once you created a string, you cannot change it later. So in the loop when you add a character to it, it’ll create a new string object each time, which is expensive. In addition, you double the string. What if the string is so long that it hardly fits in the memory? You can’t use this approach in that case.

  4. March 21, 2013 at 20:11

    Good points there, hadn’t even considered a very large string – if I implemented a program this way, if would be likely to result in a core dump if it exceeded the stack.

    Thank you :)

  1. No trackbacks yet.

Leave a Reply

Please log in using one of these methods to post your comment:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: