String to Integer (atoi)

The atoi function defined in stdlib.h in C converts a String to an int. The declaration of atoi( ) is as follows:

int atoi(const char *str);

Here we are going to write our own atoi() implementation in Java. Remember in Java you convert a string to an integer using the parseInt method of the Java Integer class. The parseInt method converts the String to an int, and throws a NumberFormatException if the string can’t be converted to an int type.

But here we will try to write the functionality using an algorithm which is different than just parsing the String to int.

  1. The function first discards all whitespace characters until the first non-whitespace character is found.
  2. Then, starting from this character, takes an optional initial plus or minus sign followed by as many numerical digits as possible, and interprets them as a numerical value.
  3. The string can contain additional characters other than numerical values, which are ignored and have no effect on the behavior of this function.
  4. If the first sequence of non-whitespace characters in str is not a valid integral number, or if the String is empty or it contains only whitespace characters, no conversion is performed.
  5. If no valid conversion could be performed, a zero value is returned.
  6. If the algorithm can convert the input String to a numerical value but which is out of range then INT_MAX (2147483647) or  INT_MIN (-2147483648) is returned.

Note:

  • Only the space character ' ' is considered a whitespace character.
  • Do not ignore any characters other than the leading whitespace or the rest of the string after the digits.

Example 1:

Input: s = "42"
Output: 42
Explanation: The underlined characters are what is read in, the caret is the current reader position.
Step 1: "42" (no characters read because there is no leading whitespace)
         ^
Step 2: "42" (no characters read because there is neither a '-' nor '+')
         ^
Step 3: "42" ("42" is read in)
           ^
The parsed integer is 42.
Since 42 is in the range [-231, 231 - 1], the final result is 42.

Example 2:

Input: s = "   -42"
Output: -42
Explanation:
Step 1: "   -42" (leading whitespace is read and ignored)
            ^
Step 2: "   -42" ('-' is read, so the result should be negative)
             ^
Step 3: "   -42" ("42" is read in)
               ^
The parsed integer is -42.
Since -42 is in the range [-231, 231 - 1], the final result is -42.

Example 3:

Input: s = "4193 with words"
Output: 4193
Explanation:
Step 1: "4193 with words" (no characters read because there is no leading whitespace)
         ^
Step 2: "4193 with words" (no characters read because there is neither a '-' nor '+')
         ^
Step 3: "4193 with words" ("4193" is read in; reading stops because the next character is a non-digit)
             ^
The parsed integer is 4193.
Since 4193 is in the range [-231, 231 - 1], the final result is 4193.

Example 4:

Input: s = "words and 987"
Output: 0
Explanation:
Step 1: "words and 987" (no characters read because there is no leading whitespace)
         ^
Step 2: "words and 987" (no characters read because there is neither a '-' nor '+')
         ^
Step 3: "words and 987" (reading stops immediately because there is a non-digit 'w')
         ^
The parsed integer is 0 because no digits were read.
Since 0 is in the range [-231, 231 - 1], the final result is 0.

Example 5:

Input: s = "-91283472332"
Output: -2147483648
Explanation:
Step 1: "-91283472332" (no characters read because there is no leading whitespace)
         ^
Step 2: "-91283472332" ('-' is read, so the result should be negative)
          ^
Step 3: "-91283472332" ("91283472332" is read in)
                     ^
The parsed integer is -91283472332.
Since -91283472332 is less than the lower bound of the range [-231, 231 - 1], the final result is clamped to -231 = -2147483648.

Constraints:

  • 0 <= s.length <= 200
  • s consists of English letters (lower-case and upper-case), digits (0-9), ' ''+''-', and '.'.
class Solution {
    public int myAtoi(String s) {
        
        //1. Empty string
        if(s == null || s.trim().isEmpty()){
            return 0;
        }
        int i = 0;
        int n = s.length();
        
        //2. Remove Spaces
        while( i < n && s.charAt(i) == ' '){
            i++;
        }
        int result = 0;
        int sign = 1;
        
         //3. Handle signs
        if(isSign(s.charAt(i))){
            sign = s.charAt(i) == '+' ? 1 : -1;
            i++;
        }
        
        //4. Convert number and avoid overflow
        while( i < n){
            int cur_digit = s.charAt(i++) - '0';
            if(cur_digit < 0 || cur_digit > 9){
                break;
            }
            
            //check if total will be overflow after 10 times and add digit
            if( result > Integer.MAX_VALUE/10 
               || (  result == Integer.MAX_VALUE/10 
                       && cur_digit > Integer.MAX_VALUE % 10)){
                return sign == 1 ? Integer.MAX_VALUE : Integer.MIN_VALUE;
            }
            result = result * 10 + cur_digit;
        }
        return result*sign;
    }
    
    private boolean isSign(char cur){
        return cur == '+' || cur == '-';
    }
}

Categories: String

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s