python 2.7 string reverse

Question

If I need to implement string reverse by myself in Python 2.7 other than using system library, wondering if any more efficient solutions? I tried my code runs slow for a very long string (e.g. a few thousand characters). Thanks.

For string reverse I mean, for example, given s = "hello", return "olleh".

def reverseString(self, s):
    """
    :type s: str
    :rtype: str
    """
    if not s:
        return ''
    temp = []
    result=''
    for i in range(len(s)-1,-1,-1):
        result += s[i]
    return result

regards, Lin

I understand that this is the reason why you try to avoid explicit loops in python. — tfv
– tfv, Commented Sep 18, 2016 at 4:57
I'm curious as to why you would need to implement this yourself, what's your reason? — shuttle87
– shuttle87, Commented Sep 18, 2016 at 5:02
When you say slow, how slow do you mean? I'm getting reasonable performance up to 50,000 length strings (less than a quarter of a second). — juanpa.arrivillaga
– juanpa.arrivillaga, Commented Sep 18, 2016 at 5:39

IanPudney · Accepted Answer · 2016-09-18 05:11:22Z

6

Try this:

def reverseString(self, s):
    return s[::-1]

edited Sep 18, 2016 at 5:11

answered Sep 18, 2016 at 4:59

IanPudney

6,0911 gold badge26 silver badges41 bronze badges

Sign up to request clarification or add additional context in comments.

3 Comments

Lin Ma Over a year ago

Thanks Ian, your solution is pretty cool, I think the issue of my code is when executing result += s[i], a new string will be created other than appending to existing string, since Python str object is constant?

Lin Ma Over a year ago

Likely? Why not completely? :)

pnovotnak Over a year ago

The 'ol double colon one-liner... A timeless Python classic! Does seem to copy the string.

user3543300 · Accepted Answer · 2016-09-18 04:58:10Z

3

Try recursion

def reverse(str):
    if str == "":
        return str
    else:
        return reverse(str[1:]) + str[0]

answered Sep 18, 2016 at 4:58

user3543300

5072 gold badges10 silver badges28 bronze badges

2 Comments

shuttle87 Over a year ago

This could be very slow depending on the size of the string and could end up breaking the max recursion limit given the inputs could be thousands of characters long.

Lin Ma Over a year ago

@shuttle87, agree with you. :)

Community · Accepted Answer · 2017-05-23 12:19:23Z

2

EDIT: Actually, I was mistaken

I did a rough-and-dirty test comparing the two functions and the complexity looks to be the same: linear

It seems that since Python 2.4, for CPython, there has been an optimisation avoiding the quadratic behavior. See the following answer to a similar question:

https://stackoverflow.com/a/37133870/5014455

What I said below is outdated for Python 2.7.

This is going to be O(n^2) because strings are immutable in Python so:

result += s[i]

Will touch ever element in the resulting string every iteration in the loop. It will be faster to build up a mutable container (e.g. a list) of individual characters and then "".join them at the end.

def reverseString(s):
    """
    :type s: str
    :rtype: str
    """
    if not s:
        return ''
    result = []
    for i in xrange(len(s)-1,-1,-1):
        result.append(s[i])
    return "".join(result)

edited May 23, 2017 at 12:19

CommunityBot

11 silver badge

answered Sep 18, 2016 at 5:02

juanpa.arrivillaga

97.6k14 gold badges141 silver badges190 bronze badges

3 Comments

Lin Ma Over a year ago

Thanks juanpa.arrivillaga, your solution is pretty cool, I think the issue of my code is when executing result += s[i], a new string will be created other than appending to existing string, since Python str object is constant?

juanpa.arrivillaga Over a year ago

@LinMa The most Pythonic solution is using slice notation (string[::-1]) But I'm not sure what restrictions you are putting on yourself for making this function. If using reversed is "cheating" then maybe slice notation would be too.

Lin Ma Over a year ago

Thanks for all the help juanpa.arrivillaga, mark your reply as answer.

Collectives™ on Stack Overflow

python 2.7 string reverse

3 Answers 3

3 Comments

2 Comments

EDIT: Actually, I was mistaken

3 Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

3 Comments

2 Comments

EDIT: Actually, I was mistaken

3 Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related