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, Sep 18 '16 at 04:57
I'm curious as to why you would need to implement this yourself, what's your reason? — shuttle87, Sep 18 '16 at 05: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, Sep 18 '16 at 05:39

IanPudney · Answer 1 · 2016-09-18T05:11:22.240

6

Try this:

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

edited Sep 18 '16 at 05:11

answered Sep 18 '16 at 04:59

IanPudney

5,941
1
24
39

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 Sep 18 '16 at 05:10
Likely? Why not completely? :) – Lin Ma Sep 18 '16 at 05:13
1

The 'ol double colon one-liner... A timeless Python classic! [Does seem to copy the string](https://docs.python.org/release/2.3.5/whatsnew/section-slices.html). – pnovotnak Sep 18 '16 at 06:17

score 3 · Answer 2 · answered Sep 18 '16 at 04:58

3

Try recursion

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

answered Sep 18 '16 at 04:58

user3543300

499
2
9
27

2

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. – shuttle87 Sep 18 '16 at 05:01
@shuttle87, agree with you. :) – Lin Ma Sep 18 '16 at 05:11

score 2 · Accepted Answer · edited May 23 '17 at 12:19

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 '17 at 12:19

Community

1
1

answered Sep 18 '16 at 05:02

juanpa.arrivillaga

88,713
10
131
172

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? – Lin Ma Sep 18 '16 at 05:10
1

@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. – juanpa.arrivillaga Sep 18 '16 at 08:21
Thanks for all the help juanpa.arrivillaga, mark your reply as answer. – Lin Ma Sep 19 '16 at 05:34

python 2.7 string reverse

3 Answers3

EDIT: Actually, I was mistaken