Reverse a string without using reversed() or [::-1]?
Solution 1
You can also do it with recursion:
def reverse(text):
if len(text) <= 1:
return text
return reverse(text[1:]) + text[0]
And a simple example for the string hello
:
reverse(hello)
= reverse(ello) + h # The recursive step
= reverse(llo) + e + h
= reverse(lo) + l + e + h
= reverse(o) + l + l + e + h # Base case
= o + l + l + e + h
= olleh
Solution 2
Just another option:
from collections import deque
def reverse(iterable):
d = deque()
d.extendleft(iterable)
return ''.join(d)
Solution 3
Use reversed range
:
def reverse(strs):
for i in xrange(len(strs)-1, -1, -1):
yield strs[i]
...
>>> ''.join(reverse('hello'))
'olleh'
xrange
or range
with -1 step would return items in reversed order, so we need to iterate from len(string)-1
to -1
(exclusive) and fetch items from the string one by one.
>>> list(xrange(len(strs) -1, -1 , -1))
[4, 3, 2, 1, 0] #iterate over these indexes and fetch the items from the string
One-liner:
def reverse(strs):
return ''.join([strs[i] for i in xrange(len(strs)-1, -1, -1)])
...
>>> reverse('hello')
'olleh'
Solution 4
EDIT
Recent activity on this question caused me to look back and change my solution to a quick one-liner using a generator:
rev = ''.join([text[len(text) - count] for count in xrange(1,len(text)+1)])
Although obviously there are some better answers here like a negative step in the range or xrange function. The following is my original solution:
Here is my solution, I'll explain it step by step
def reverse(text):
lst = []
count = 1
for i in range(0,len(text)):
lst.append(text[len(text)-count])
count += 1
lst = ''.join(lst)
return lst
print reverse('hello')
First, we have to pass a parameter to the function, in this case text
.
Next, I set an empty list, named lst
to use later. (I actually didn't know I'd need the list until I got to the for
loop, you'll see why it's necessary in a second.)
The count
variable will make sense once I get into the for
loop
So let's take a look at a basic version of what we are trying to accomplish:
It makes sense that appending the last character to the list would start the reverse order. For example:
>>lst = []
>>word = 'foo'
>>lst.append(word[2])
>>print lst
['o']
But in order to continue reversing the order, we need to then append word[1]
and then word[0]
:
>>lst.append(word[2])
>>lst.append(word[1])
>>lst.append(word[0])
>>print lst
['o','o','f']
This is great, we now have a list that has our original word in reverse order and it can be converted back into a string by using .join()
. But there's a problem. This works for the word foo, it even works for any word that has a length of 3 characters. But what about a word with 5 characters? Or 10 characters? Now it won't work. What if there was a way we could dynamically change the index we append so that any word will be returned in reverse order?
Enter for loop.
for i in range(0,len(text)):
lst.append(text[len(text)-count])
count += 1
First off, it is necessary to use in range()
rather than just in
, because we need to iterate through the characters in the word, but we also need to pull the index value of the word so that we change the order.
The first part of the body of our for loop should look familiar. Its very similar to
>>lst.append(word[..index..])
In fact, the base concept of it is exactly the same:
>>lst.append(text[..index..])
So what's all the stuff in the middle doing?
Well, we need to first append the index of the last letter to our list, which is the length of the word, text
, -1. From now on we'll refer to it as l(t) -1
>>lst.append(text[len(text)-1])
That alone will always get the last letter of our word, and append it to lst
, regardless of the length of the word. But now that we have the last letter, which is l(t) - 1, we need the second to last letter, which is l(t) - 2, and so on, until there are no more characters to append to the list. Remember our count
variable from above? That will come in handy. By using a for
loop, we can increment the value of count
by 1 through each iteration, so that the value we subtract by increases, until the for loop has iterated through the entire word:
>>for i in range(0,len(text)):
..
.. lst.append(text[len(text)-count])
.. count += 1
Now that we have the heart of our function, let's look at what we have so far:
def reverse(text):
lst = []
count = 1
for i in range(0,len(text)):
lst.append(text[len(text)-count])
count += 1
We're almost done! Right now, if we were to call our function with the word 'hello', we would get a list that looks like:
['o','l','l','e','h']
We don't want a list, we want a string. We can use .join
for that:
def reverse(text):
lst = []
count = 1
for i in range(0,len(text)):
lst.append(text[len(text)-count])
count += 1
lst = ''.join(lst) # join the letters together without a space
return lst
And that's it. If we call the word 'hello' on reverse(), we'd get this:
>>print reverse('hello')
olleh
Obviously, this is way more code than is necessary in a real life situation. Using the reversed function or extended slice would be the optimal way to accomplish this task, but maybe there is some instance when it would not work, and you would need this. Either way, I figured I'd share it for anyone who would be interested.
If you guys have any other ideas, I'd love to hear them!
Solution 5
Only been coding Python for a few days, but I feel like this was a fairly clean solution. Create an empty list, loop through each letter in the string and append it to the front of the list, return the joined list as a string.
def reverse(text):
backwardstext = []
for letter in text:
backwardstext.insert(0, letter)
return ''.join(backwardstext)
samrap
http://mattgemmell.com/2008/12/08/what-have-you-tried/ What is the best comment in source code you have ever encountered?
Updated on July 09, 2022Comments
-
samrap almost 2 years
I came across a strange Codecademy exercise that required a function that would take a string as input and return it in reverse order. The only problem was you could not use the reversed method or the common answer here on stackoverflow,
[::-1]
.Obviously in the real world of programming, one would most likely go with the extended slice method, or even using the
reversed
function but perhaps there is some case where this would not work?I present a solution below in Q&A style, in case it is helpful for people in the future.
-
samrap over 10 yearscan you explain the xrange part? I saw a similar answer in another post but didn't understand what was going on
-
Blender over 10 yearsRecursive golf:
f=lambda t:len(t)>1and f(t[1:])+t[0]or t
-
Burhan Khalid over 10 yearsYou don't need that inner list.
-
Ashwini Chaudhary over 10 years@BurhanKhalid For efficiency purpose we do.
-
Burhan Khalid over 10 yearsThis is a case of premature optimization.
-
samrap over 10 yearswow this is the coolest answer on here, very unique. One question though, why is it join item[1] and not just join item?
-
Brian Peterson over 10 yearsBest answer by far. Python wasn't geared for this kind of low-level programming without the use of its helpful constructs, but this is by far the best way to do so if you must.
-
CT Zhu over 10 yearsThe
item
s will be like(0,'a')
, tuples of aint
(the index) and astr
(the value), so you can't just.join()
them. :-P -
Ketan Maheshwari over 10 yearsI think this line is missing a
-1
in the subscript oftext
:lst.append(text[len(text)-count])
-
samrap over 10 yearsNo, that would only be necessary if
count
started at 0, it starts at 1 -
samrap over 10 yearsLooking back, this can be reduced to one line:
[text[len(text) - count] for count in xrange(1,len(text)+1)]
-
Ketan Maheshwari over 10 yearsTrue. I find this slightly changed version more readable somehow:
[text[len(text) - 1 - count] for count in xrange(len(text))]
-
samrap over 10 yearsDefinitely more readable, though now that I have more Python experience I would go with a more readable comprehension like some of the answers here
-
samrap about 10 yearsThat's great! Keep up the work, Codecademy was a great resource for me
-
samrap about 10 yearsThat's a good one, one way to save the string more elegantly would be to turn your loop into a list comprehension and then return a str of the list with the
join
function:return ''.join([x[n] for n in range(len(x)-1, -1, -1)])
This is a simple one-liner. Also there is no need forstr()
in your range assuming x is already a string. Not sure if you've done list comprehensions yet in Python. When you have this will make more sense. Great job! :) -
Fadeiar about 10 yearsThank's a lot for your reply i have just moved on with the challenges on codeacademy and I could really make use of your hint :). After reading a little bit on list comprehension I was able to use your input for a function that kicks out all vowels in a string.
def anti_vowel(text): vowels = "aeiou" return "".join(n for n in text if not n.lower() in vowels)
Thanks a lot @samrap (can't give reputation points yet) -
samrap almost 10 yearsnice! I'm so stoked that people continue to find this a useful and interesting thread. Love seeing all the answers!
-
Emanuele Paolini almost 10 yearsI think this solution requires O(n^2) memory... this could be very bad for long strings.
-
Deepend almost 10 yearsIt is better for the OP if you can add some more information on an Answer such as this. Others looking at this in future will all benefit.
-
Blender almost 10 years@EmanuelePaolini:
[::-1]
is the only thing you should be using. All of these answers are just different ways of reversing a string, there are no speed guarantees. -
samrap almost 10 yearsAgreed with @deepend also I like this answer it is similar to the way it is done in K&R's C Programming Language book
-
samrap over 9 years+1 Didn't even know you could do this, or maybe I did at one point I just haven't worked with Python in 4 or 5 months. Either way, good job
-
samrap over 9 yearsNice one! Liking the creativity on this one
-
AdjunctProfessorFalcon almost 9 years@Blender Thanks for this breakdown, appreciate it. Just to be clear on what's happening here: is the text variable for
text[0
] basically storing each character it slices off as the recursive function calls keeps cycling through the string? or is it that with each recursive call anothertext[0]
is being added? -
Blender almost 9 years@ChrisPurrone: The recursive function doesn't really "cycle" through the string (in CPython). Each time you call a function, a stack frame is created (which contains the local variables and the return value of your function). Your function is recursive, so each time you
return
something a new stack frame is created, but since the return value is dependent on another function's return value, the old stack frames still need to stick around. That's why I wrote the long chain of+ h
's. They aren't really concatenated until the very end, which is when the final function call returns a string. -
AdjunctProfessorFalcon almost 9 years@Blender So how you have all the strings being concatenated (until the final function call) is really just an way of describing how the strings that are sliced off by the
text[0]
are being stored in memory in each stack frame? Why is it that all the strings are only concatenated at the very end instead each string (in each stack frame) being added together? Sorry, newbie so struggling to understand how reverse(text[1:]0 and text[0] are working together here. -
Blender almost 9 years@ChrisPurrone: CPython doen't do any sort of recursion optimization at all (from what I remember). In fact, CPython doesn't even optimize tail recursive functions, which can be translated easily into equivalent iterative functions.
-
krethika almost 9 yearsFor my solution, I refactored this into a while loop to avoid recursion error on long strings.
-
Pang over 8 yearsThe question says "without using reversed or
[::-1]
". -
simple noobie over 8 yearsMy original query was how to reverse a string and this is where I was led.
-
Amit about 6 yearsOne of the fastest.
-
Amit about 6 yearsSimplest and one of the fastest!
-
SamTheProgrammer over 2 yearsDon't use
str
for a variable since it is already part of the Python keywords list. Try usingnew_string