String to Integer (atoi)


  • 0
    T

    Solution in Python

    Cases to handle

    • leading white spaces in the input string have to be removed
    • First non-whitespace character could be an optional '+' or '-' symbol indicating sign of the number followed by as many numerical digits as possible which is interpreted as a numeric value.
    • Additional characters after those that form the integral number, should be ignored and should have no effect on the behavior of this function
    • If no valid conversion could be performed, a zero value is returned.
    • If the correct value is out of the range of representable values, INT_MAX (2147483647) or INT_MIN (-2147483648) is returned.

    Approach #1 (Regex) [Accepted]

    The regex approach uses the re module from the python standard library. We write a regular expression to match all strings that have leading white spaces followed by an optional '+' or '-' followed by digits.
    We use a try-catch block to handle the condition that If no valid conversion could be performed, a zero value is returned.
    Once we get the desired string, it can be converted to an integer and returned after checking for overflow conditions.

    def myAtoi(self, str):
     
        try:
            a = int(re.match(r'\s*[\+|-]?\d*',str).group())
                 
            if a>2147483647:
                return 2147483647
            if a<-2147483648:
                return -2147483648
            return a
        except:
            return 0
    

    Complexity Analysis

    • Time complexity : O(2n) = O(n). In the worst case each character will be visited twice. First for regex pattern matching and then for casting the string obtained by the regex to int.
    • Space complexity : O(n). In the worst case (assuming all characters in the input string are numbers , we will be storing n element string in memory which we obtain as the output of the regex.

    Approach #2 (character comparison) [Accepted]

    The previous approach suffered from the draw back that we were visiting each character twice.
    The solution can be improved upon by removing the dependency on the re module.

    Mathematically - The number can be built from each digit obtained in sequence using the following formula -

                                         num = num *10 + digit
    

    where num is initialized to zero and digit is each numeric character obtained from the string as we read the string from left to right

        An Integer `1234` can be formed as shown below.
        Step1: 1
        Step2: 1*10 + 2 = 10 + 2 = 12
        Step3: 12*10 + 3 = 120 + 3 = 123
        Step4: 123*10 + 4 = 1230 + 4 = 1234
    
        def myAtoi(self, str):
            res = 0
            str = str.lstrip()
            try:
                if str[0] == '+':
                    sign = 1
                elif str[0] == '-':
                    sign = -1
                elif 48<=ord(str[0])<=57:
                    sign = 1
                    res = res*10 + (ord(str[0])-48)
                else:
                    return 0
                for ch in str[1::]:
                    if 48<=ord(ch)<=57:
                        res=res*10+(ord(ch)-48)
                    else:
                        break
                
                if (res*sign)>2147483647:
                    return 2147483647
                elif (res*sign)<-2147483648:
                    return -2147483648
                else:
                    return res*sign
    
            except:
                return 0                                                                                                                         
    

    Complexity Analysis

    • Time complexity : O(n) . In the worst case each character will be visited once.
    • Space complexity : O(1) This is a constant time algorithm as the memory usage is independent of the size of the input string.

    Approach #3 (character comparison - without built-in functions) [Accepted]

    The above solution can be rewritten to remove the dependency on the function str.lstrip().

    We use an additional variable that helps us break out of the loop if there is a space character after numeric digits in the string but if the same space is present as a leading space in the input string we pass over to next character until we encounter a non-white space character.
    The time and space complexity remains the same as Approach 2.

    def myAtoi(self, str):
        res = 0
        temp = 0
        temp1 = 0
        sign = 1
        if str == "":
            return 0
        try:
                for ch in str:
                    if temp>=2:
                        return res
                    elif ch==" ":
                        if (temp>=1) or (temp1>0):
                            break
                    
                        else:
                            pass
                    elif ch == "+":
                        temp = temp+1
                        sign = 1
                        
                    elif ch == "-":
                        sign = -1
                        temp = temp+1
                    elif 48<=ord(ch)<=57:
                        temp1 = temp1+1
                        res = res*10 + (ord(ch)-48)
                    else:
                        break
                    
                sum = res*sign
                
                if sum>2147483647:
                    return 2147483647
                elif sum<-2147483648:
                    return -2147483648
                else:
                    return sum
        except:
            return 0
    

    Complexity Analysis

    • Time complexity : O(n) . In the worst case each character will be visited once.
    • Space complexity : O(1) This is a constant time algorithm as the memory usage is independent of the size of the input string.

Log in to reply
 

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