python 2.7 string reverse
<p>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.</p>

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

<pre><code>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
</code></pre>

<p>regards,
Lin</p>

<h2>EDIT: Actually, I was mistaken</h2>

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

<p><a href="http://i.stack.imgur.com/sZttR.png" rel="nofollow"><img src="http://i.stack.imgur.com/sZttR.png" alt="enter image description here"></a></p>

<p>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:</p>

<p><a href="http://stackoverflow.com/a/37133870/5014455">http://stackoverflow.com/a/37133870/5014455</a></p>

<p><strong>What I said below is outdated for Python 2.7.</strong></p>

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

<pre><code>result += s[i]
</code></pre>

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

<pre><code>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)
</code></pre>

python python-2.7