Why my python's code goes so slowly?


  • 0
    T

    class Solution:

    def calculate(self, s):
        def calSimple(s1,position):
            val = 0
            op = '+'
            tmpVal = 0
            i=0
            while i<len(s1):
                if s1[i]<='9' and s1[i]>='0':
                    tmpVal= tmpVal*10+int(s1[i])
                elif s1[i]=='+':
                    if op=='+':
                        val+=tmpVal
                    else:
                        val-=tmpVal
                    tmpVal = 0
                    op='+'
                elif s1[i]=='-':
                    if op=='+':
                        val+=tmpVal
                    else:
                        val-=tmpVal
                    tmpVal = 0
                    op='-'
                elif s1[i]==')':
                    if op=='+':
                        val+=tmpVal
                    else:
                        val-=tmpVal
                    return val,position+i
                elif s1[i]=='(':
                   
                    val1,tmpi = calSimple(s1[i+1:],position+i+1)
                    i=tmpi-position
                    if op=='+':
                        val+=val1
                    else:
                        val-=val1
                i+=1
            if op=='+':
                return val+tmpVal,position+i
            else:
                return val-tmpVal,position+i
        val1,tmpi=calSimple(s,0)
        return val1

  • 0
    T

    In my computer, it runs very fast for the "Time Exceed" test case.


  • 1

    "In my computer, it runs very fast for the "Time Exceed" test case."

    I'm pretty sure that's not true. It's a huge case, and your algorithm's runtime is quadratic.

    Every recursive call with s1[i+1:] makes a copy of that entire substring. That takes a lot of time (and memory, btw). Better only work with the single original string.


  • 0
    T

    Thanks , I realized that yesterday and finally Accept :)


Log in to reply
 

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