STOI String to Integer

96.String to Integer (atoi)

String

Problem Statement:

Implement the myAtoi function, which converts a string to a 32-bit signed integer (similar to the atoi function in C/C++). The function discards leading whitespace, considers an optional sign, and processes numerical digits until a non-digit character or the end of the string is encountered. If the converted value exceeds the range of a 32-bit signed integer, clamp it to [-2³¹, 2³¹ - 1].

Algorithm:

1. Handle edge cases, such as empty strings, by returning 0.
2. Remove leading whitespace characters by iterating over the string until a non-space character is encountered.
3. Determine the sign of the number by checking for '+' or '-' characters. Default to positive if no sign is present.
4. Convert the numerical portion of the string to an integer, stopping when a non-digit character is encountered or an overflow is detected.
5. Clamp the result to the range [-2³¹, 2³¹ - 1] if necessary and return the final value.

Complexity:

Time: O(n), where n is the length of the string | Space: O(1).

Java Implementation:

public int myAtoi(String str) {
    int index = 0, sign = 1, total = 0;

    // 1. Empty string
    if (str.length() == 0) return 0;

    // 2. Remove leading spaces
    while (index < str.length() && str.charAt(index) == ' ')
        index++;

    // 3. Handle signs
    if (index < str.length() && (str.charAt(index) == '+' || str.charAt(index) == '-')) {
        sign = str.charAt(index) == '+' ? 1 : -1;
        index++;
    }

    // 4. Convert number and handle overflow
    while (index < str.length()) {
        int digit = str.charAt(index) - '0';

        // Break if the character is not a digit
        if (digit < 0 || digit > 9) break;

        // Check for overflow
        if (Integer.MAX_VALUE / 10 < total || (Integer.MAX_VALUE / 10 == total && Integer.MAX_VALUE % 10 < digit))
            return sign == 1 ? Integer.MAX_VALUE : Integer.MIN_VALUE;

        total = 10 * total + digit;
        index++;
    }

    return total * sign;
}

Python Implementation:

def myAtoi(s):
    index, sign, total = 0, 1, 0
    INT_MAX, INT_MIN = 2**31 - 1, -2**31

    # 1. Empty string
    if not s:
        return 0

    # 2. Remove leading spaces
    while index < len(s) and s[index] == ' ':
        index += 1

    # 3. Handle signs
    if index < len(s) and s[index] in ['+', '-']:
        sign = 1 if s[index] == '+' else -1
        index += 1

    # 4. Convert number and handle overflow
    while index < len(s) and s[index].isdigit():
        digit = int(s[index])

        # Check for overflow
        if total > (INT_MAX - digit) // 10:
            return INT_MAX if sign == 1 else INT_MIN

        total = total * 10 + digit
        index += 1

    return total * sign

C++ Implementation:

#include 
#include 
using namespace std;

int myAtoi(string s) {
    int index = 0, sign = 1, total = 0;

    // 1. Empty string
    if (s.empty()) return 0;

    // 2. Remove leading spaces
    while (index < s.size() && s[index] == ' ')
        index++;

    // 3. Handle signs
    if (index < s.size() && (s[index] == '+' || s[index] == '-')) {
        sign = (s[index] == '+') ? 1 : -1;
        index++;
    }

    // 4. Convert number and handle overflow
    while (index < s.size() && isdigit(s[index])) {
        int digit = s[index] - '0';

        // Check for overflow
        if (total > (INT_MAX - digit) / 10)
            return (sign == 1) ? INT_MAX : INT_MIN;

        total = total * 10 + digit;
        index++;
    }

    return total * sign;
}