8. String to Integer (atoi)

Description

The problem is to implement the function myAtoi which converts a string to a 32-bit signed integer (similar to C/C++'s atoi function). The function needs to handle whitespace, optional signs, and the conversion of digits to an integer. Additionally, it must manage overflow by clamping the integer within the 32-bit signed integer range, returning -2147483648 or 2147483647 when the integer is out of bounds.

Intuition

The core of this problem is to parse a string to extract an integer while respecting the constraints of the 32-bit signed integer range. Handling edge cases such as leading whitespaces, signs, and non-digit characters is crucial. The conversion must also be stopped as soon as a non-digit character is encountered, ensuring the result is within the valid range.

Approach

1. Trim leading whitespace: Skip any leading spaces in the input string.
2. Handle the optional sign: Check if the next character is a sign (+ or -) and determine if the resulting number should be positive or negative.
3. Convert digits to an integer: Iterate through the string, converting each digit to an integer and forming the final number.
4. Check for overflow: During the conversion, continuously check if the integer exceeds the bounds of a 32-bit signed integer. If it does, return the respective boundary value.
5. Return the final integer: Once the conversion is complete, return the integer with the appropriate sign.

Complexity

Time Complexity:

O(N), where N is the length of the input string. The function processes each character of the string once.

Space Complexity:

O(1), as the conversion process requires a constant amount of additional space.

Code

C++

class Solution {
public:
    int myAtoi(string s) {
        long ans = 0;
        int sign = 1;
        int i = 0;

        // Skip leading whitespace
        while (i < s.length() && s[i] == ' ') i++;

        // Check for sign
        if (i < s.length() && (s[i] == '-' || s[i] == '+')) {
            sign = (s[i] == '-') ? -1 : 1;
            i++;
        }

        // Convert the digits to an integer
        while (i < s.length() && isdigit(s[i])) {
            ans = ans * 10 + (s[i] - '0');
            if (ans * sign <= INT_MIN) return INT_MIN;
            if (ans * sign >= INT_MAX) return INT_MAX;
            i++;
        }

        return ans * sign;
    }
};

Python

class Solution:
    def myAtoi(self, s: str) -> int:
        ans = 0
        sign = 1
        i = 0
        n = len(s)

        # Skip leading whitespace
        while i < n and s[i] == ' ':
            i += 1

        # Check for sign
        if i < n and (s[i] == '-' or s[i] == '+'):
            sign = -1 if s[i] == '-' else 1
            i += 1

        # Convert the digits to an integer
        while i < n and s[i].isdigit():
            ans = ans * 10 + int(s[i])
            if ans * sign <= -2**31:
                return -2**31
            if ans * sign >= 2**31 - 1:
                return 2**31 - 1
            i += 1

        return ans * sign

Java

class Solution {
    public int myAtoi(String s) {
        long ans = 0;
        int sign = 1;
        int i = 0;

        // Skip leading whitespace
        while (i < s.length() && s.charAt(i) == ' ') i++;

        // Check for sign
        if (i < s.length() && (s.charAt(i) == '-' || s.charAt(i) == '+')) {
            sign = (s.charAt(i) == '-') ? -1 : 1;
            i++;
        }

        // Convert the digits to an integer
        while (i < s.length() && Character.isDigit(s.charAt(i))) {
            ans = ans * 10 + (s.charAt(i) - '0');
            if (ans * sign <= Integer.MIN_VALUE) return Integer.MIN_VALUE;
            if (ans * sign >= Integer.MAX_VALUE) return Integer.MAX_VALUE;
            i++;
        }

        return (int) ans * sign;
    }
}

JavaScript

let myAtoi = function (s) {
    const ans = Number.parseInt(s);
    if (ans) {
        if (ans <= -2147483648) return -2147483648;
        else if (ans >= 2147483647) return 2147483647;
        else return ans;
    }
    return 0;
};