A DP solution for python


  • 0
    P
    class Solution(object):
        def myAtoi(self, str):
            """
            :type str: str
            :rtype: int
            """
            # Use DP
            # dp[i] is the current number up to str[i-1] (str[:i])
            str = str.strip()
            sign = 1 # 1 is pos; -1 is neg
            if not str:
                return 0
            dp = [0 for x in xrange(len(str)+1)]
            for i in xrange(len(str)):
                if str[i].isdigit():
                    dp[i+1] = dp[i]*10 + int(str[i])
                elif str[i] in "+-":
                    if i != 0: # start
                        return self.overflowcheck(dp[i]*sign) # return last dp
                    if str[i] == "-":
                        sign = -1
                else: # for other non-digit, return
                    return self.overflowcheck(dp[i]*sign)
            return self.overflowcheck(dp[-1]*sign)
        def overflowcheck(self, num):
            if num < 0:
                return max(-2147483648, num)
            else:
                return min(2147483647, num)

Log in to reply
 

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