🎨 Try our Free AI Image Generation Feature

8. String to Integer (atoi)

avatar
Dare2Solve

10 months ago

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;
};