CODEWITHSUNDEEP
pythonpython-2.7
Lin Ma
Lin Ma

Reputation: 10139

python 2.7 string reverse

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

Upvotes: 0

Views: 1135

Answers (3)

juanpa.arrivillaga
juanpa.arrivillaga

Reputation: 95863

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

enter image description here

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)

Upvotes: 2

IanPudney
IanPudney

Reputation: 6021

Try this:

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

Upvotes: 6

user3543300
user3543300

Reputation: 507

Try recursion

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

Upvotes: 3

Related Questions