8. String to Integer (atoi) Medium

Implement the myAtoi(string s) function, which converts a string to a 32-bit signed integer.

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

• Whitespace: Read in and ignore any leading whitespace (" ").
• Signedness: Determine the sign by checking if the next character is '-' or '+', assuming positivity if neither is present.
• Conversion: 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.
• Rounding: If the integer is out of the 32-bit signed integer range [-2^31, 2^31 - 1], then clamp the integer so that it remains in the range. Specifically, integers less than -2^31 should be clamped to -2^31, and integers greater than 2^31 - 1 should be clamped to 2^31 - 1.

Return the integer as the final result.

Example 1:
Input: s = "42"
Output: 42
Explanation: The bold 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" (read in "42")

Example 2:
Input: s = " -042"
Output: -42
Explanation:
Step 1: " -042" (leading whitespace is read and ignored)
Step 2: " -042" ('-' is read, so the result should be negative)
Step 3: " -042" ("042" is read in, leading zeros ignored in the result)

Example 3:
Input: s = "1337c0d3"
Output: 1337
Explanation:
Step 1: "1337c0d3" (no characters read because there is no leading whitespace)
Step 2: "1337c0d3" (no characters read because there is neither a '-' nor '+')
Step 3: "1337c0d3" ("1337" is read in; reading stops because the next character is a non-digit)

Example 4:
Input: s = "0-1"
Output: 0
Explanation:
Step 1: "0-1" (no characters read because there is no leading whitespace)
Step 2: "0-1" (no characters read because there is neither a '-' nor '+')
Step 3: "0-1" ("0" is read in; reading stops because the next character is a non-digit)

Example 5:
Input: s = "words and 987"
Output: 0
Explanation:
Reading stops at the first non-digit character 'w'.

Approach

Input: A string s

Output: Implement a function to convert the string s into a 4-byte integer.

This problem belongs to String problems.

1. Skip leading whitespaces
2. Handle the sign bit
3. Read the numbers
   • num = num * 10 + current digit
4. Prevent overflow
   • For positive: num > (INT_MAX - digit) / 10
   • For negative: num > (INT_MAX + 1 - digit) / 10
5. Return result

Implementation

python

class Solution:
    def myAtoi(self, s: str) -> int:
        # The 32-bit integer range required by the problem
        MAX_INT = 2 ** 31 - 1   # 2147483647
        MIN_INT = -2 ** 31      # -2147483648

        i, n = 0, len(s)

        # 1. Skip leading whitespaces
        while i < n and s[i] == ' ':
            i += 1
        # If string is entirely whitespaces, return 0
        if i == n:
            return 0

        # 2. Read the sign bit (+ or -)
        sign = 1
        if s[i] == '-' or s[i] == '+':
            sign = -1 if s[i] == '-' else 1
            i += 1

        # 3. Read consecutive digit characters and build result
        num = 0
        while i < n and '0' <= s[i] <= '9':
            digit = int(s[i])  # Current digit

            # 4. Overflow check (check beforehand to avoid exceeding range after num*10)
            if sign == 1 and num > (MAX_INT - digit) // 10:
                return MAX_INT
            if sign == -1 and num > (MAX_INT + 1 - digit) // 10:
                return MIN_INT

            # Accumulate result
            num = num * 10 + digit
            i += 1

        # 5. Return signed result
        return sign * num

javascript

/**
 * @param {string} s
 * @return {number}
 */
var myAtoi = function(s) {
    // 32-bit signed integer range
    const MAX = 2 ** 31 - 1;   // 2147483647
    const MIN = -(2 ** 31);    // -2147483648

    let i = 0;  // Current scanning pointer
    
    // 1. Skip leading spaces
    while (i < s.length && s[i] === ' ') i++;
    // If reached end after skipping spaces, return 0
    if (i == s.length) return 0;

    // 2. Read sign bit (+ or -)
    let sign = 1;
    if (s[i] === '-' || s[i] === '+') {
        sign = s[i] === '-' ? -1 : 1;
        i++;
    }

    // 3. Read consecutive digits
    let num = 0;
    while (i < s.length && /[0-9]/.test(s[i])) {
        const d = Number(s[i]);  // Convert current char to a number

        // 4. Overflow check (early exit to avoid exceeding logic limitations safely)
        if (sign === 1 && num > (MAX - d) / 10) return MAX;
        if (sign === -1 && num > (MAX + 1 - d) / 10) return MIN;

        // Number aggregation accumulation
        num = num * 10 + d;
        i++;
    }

    // 5. Final calculation output determining values correctly
    return sign * num;
};

Complexity Analysis

• Time Complexity: O(n)
• Space Complexity: O(1)

Links

8. String to Integer (atoi) (English)

8. 字符串转换整数 (atoi) (Chinese)