Python. time exceeded


  • 0
    P
    class Solution(object):
        def reverseString(self, s):
            str=''
            for i in range(len(s)-1,-1,-1):
                str=str+s[i]
            return str
    

    I get the time limit exceeded error. Not sure how/why!


  • -1
    A

    Because you're using a loop when it's not necessary.
    I'll give you a gooood hint: try slicing instead!


  • 0
    H

    but why the loop solution is considered TLE? or why the slicing solution is faster? because the implementation of python interpreter does optimization for slicing?


  • 1
    B

    I think appending operation is slow, putting it in a loop is even slower.
    In java, if you do things like this, you will end up creating new String over and over again as String is a immutable type. A StringBuilder will be much faster since it's mutable.
    There is no such thing like StringBuilder in Python, but I think String in Python is also immutable, so appending it is also as slow as doing so in Java


  • 0
    X

    @billcode That is true. I converted the string to a list and did in-place reversal then converted it back. It was accepted.


  • 0
    R

    Because if you do str = str + s[i], each time str grows length 1, python and most other programming languages will make a new string by copying the old string, which is certainly not necessary. Instead if you read something about Java StringBuilder, you can adopt the same idea in python.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.