String To Integer (atoi) Problem

Difficulty – Medium

String To Integer (atoi) Problem: Implement the myAtoi(string s) function, which converts a string to a 32-bit signed integer (similar to C/C++’s atoi function).

The algorithm for myAtoi(string s) is as follows:

• Read in and ignore any leading whitespace.
• Check if the next character (if not already at the end of the string) is ‘-‘ or ‘+’. Read this character in if it is either. This determines if the final result is negative or positive respectively. Assume the result is positive if neither is present.
• Read in next the characters until the next non-digit character or the end of the input is reached. The rest of the string is ignored.
• Convert these digits into an integer (i.e. “123” -> 123, “0032” -> 32). If no digits were read, then the integer is 0. Change the sign as necessary (from step 2).
• If the integer is out of the 32-bit signed integer range [-231, 231 – 1], then clamp the integer so that it remains in the range. Specifically, integers less than -231 should be clamped to -231, and integers greater than 231 – 1 should be clamped to 231 – 1.
• Return the integer as the final result.

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.

String To Integer (atoi) Problem Solution

Problem solution in Python

class Solution:
    def validCharacter(self, ch):
        return ord('0') <= ord(ch) <= ord('9')
    
    def myAtoi(self, s: str) -> int:
        l = list(s)
        
        # remove whitespace
        while l and l[0] == " ":
            l.pop(0)
            
        # specify sign
        sign = 1
        if l and l[0] == '+':
            l.pop(0)
            sign = 1
        elif l and l[0] == '-':
            l.pop(0)
            sign = -1
        
        buf = ""
        while l and self.validCharacter(l[0]):
            buf += l.pop(0)
        
        result = 0
        for i in buf:
            num = ord(i) - ord('0')
            result = result* 10 + num
        result *= sign  # add sign
        if result > 2 ** 31 - 1:
            return 2 ** 31 - 1
        elif result < -(2 ** 31):
            return -(2 ** 31)
        else:
            return result

Problem solution in Java

int start = 0, sign = 1;
        long res = 0;
        while(start < s.length() && s.charAt(start) == ' ') {
            start++;
        }
        
        if(start < s.length() && s.charAt(start) == '+') {
            start++;
        } else if(start < s.length() && s.charAt(start) == '-') {
            sign = -1;
            start++;
        }
        
        while(start < s.length()) {
            if(!Character.isDigit(s.charAt(start))) break;
            res *= 10;
            res += s.charAt(start) - '0';
            if(res > Integer.MAX_VALUE) {
                if(sign == 1) return Integer.MAX_VALUE;
                return Integer.MIN_VALUE;
            }
            start++;
        }
        
        return (int) res * sign;

Problem solution in C++

class Solution {
public:
    int myAtoi(string str) {
        long long ans =0;
        bool isNeg = false;
        int i=0;
        while(str[i]==' ')
            i++;
        
        if(str[i]=='-'){
            isNeg = true;
            i++;
        }
            
        else if(str[i]=='+'){
            isNeg = false;
            i++;
        }
        while(str[i]=='0')
            i++;
        
        int end=0;
        for( end=i;end<str.size();end++){
             if(str[end]>'9'||str[end]<'0')
            break;
        }
        if(end-i>12){
            if(isNeg)
                return INT_MIN;
            else return INT_MAX;
        }
        for(int j=i;j<str.size();j++){
          if(str[j]>'9'||str[j]<'0')
            break;
            
            ans = 10*ans + str[j]-'0';
           
        }
         if(isNeg)
                return (INT_MIN>-ans?INT_MIN:-ans);
            else
                return (INT_MAX>ans?ans:INT_MAX);
       
    }
};

Problem solution in C

int myAtoi(char *str) {
    int flag = 1;
    long res = 0;
    
    if (str == NULL) return 0;
    while (*str == ' ' || *str == '\t') ++str;
    if (str == NULL) return 0;
    if (*str != '-' && *str != '+' && (*str < '0' || *str >'9')) return 0; 
    if (*str == '-') {flag = -1;++str;}
    else if (*str == '+') {flag = 1; ++str;}
    if (str == NULL) return 0;
    
    int cnt = 0;  
    while(*str) {
        if (*str < '0' || *str >'9') break;
        res = res * 10 + *str - 0x30;
        ++str;
        ++cnt;
    }
    
    if (cnt > 10) return flag == 1 ? INT_MAX : INT_MIN;
    
    res *= flag;
    if (res > INT_MAX) return INT_MAX;
    if (res < INT_MIN) return INT_MIN;
    

    return (int)res;
}