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.

  • 0
    R
    public static int myAtoi(String str) {
         int result = 0;
         boolean isSigned = false;
         int i = 0;
         if(str != null && str.length() > 0) {
            if(str.charAt(0) == '-' || str.charAt(0) =='+') {
    	   i++;
    	   if(str.charAt(0) == '-') {
    		isSigned = true;
    	   }
    	 }	
    	 while(i < str.length()) {
    	    if(str.charAt(i) == ' ') {
    		i++;
    		continue;
    	    }
    	    int value = (int)str.charAt(i) - 48;
    	    if(value >= 0 && value <= 9) {
    		result = result * 10 + value;
    	    } else {
    		return 0;
    	    }
    		i++;
    	   }
           }
           if(isSigned) {
    	 result = 0 - result;
           }
      return result;
    }

Log in to reply
 

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