String to Integer (atoi) medium

Problem Statement

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

The algorithm for myAtoi is as follows:

1. Read in and ignore any leading whitespace.
2. 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.
3. 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.
4. Convert these digits into an integer (i.e., "123" -> 123). If no digits were read, then the integer is 0. Change the sign as necessary (from step 2).
5. If the integer is out of the 32-bit signed integer range [-2³¹, 2³¹ - 1], then clamp the integer so that it remains in the range. Specifically, integers less than -2³¹ should be clamped to -2³¹, and integers greater than 2³¹ - 1 should be clamped to 2³¹ - 1.
6. Return the integer as the result.

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 leading whitespace) ^ Step 2: "42" (no +/- sign) ^ Step 3: "42" ("42" is read in) ^ Step 4: 42 (no sign, so positive) Step 5: 42 (in range) Step 6: 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) ^ Step 4: -42 (the result is negative) Step 5: -42 (in range) Step 6: -42

Steps

1. Whitespace Removal: Iterate through the string until a non-whitespace character is found.
2. Sign Detection: Check if the next character is '+' or '-'. Store the sign (1 for positive, -1 for negative).
3. Digit Extraction: Iterate through the string, reading digits until a non-digit character is encountered.
4. Integer Conversion: Convert the extracted digits to an integer.
5. Range Check and Clamping: Check if the integer is within the 32-bit signed integer range. Clamp if necessary.

Explanation

The C++ code meticulously follows the steps outlined in the problem description. Error handling is crucial to manage edge cases such as empty strings, strings with only whitespace, and strings containing non-digit characters after digits. The isdigit function from <cctype> is used to efficiently determine if a character is a digit. The long long data type is used to prevent overflow during the conversion process before clamping to the int range.

Code

#include <iostream>
#include <string>
#include <cctype>
#include <limits>

using namespace std;

int myAtoi(string s) {
    long long result = 0;
    int sign = 1;
    int i = 0;

    // 1. Whitespace removal
    while (i < s.length() && isspace(s[i])) {
        i++;
    }

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

    // 3. Digit extraction and conversion
    while (i < s.length() && isdigit(s[i])) {
        result = result * 10 + (s[i] - '0');
        i++;
        //Early check for overflow before final check
        if(result * sign > numeric_limits<int>::max()) return numeric_limits<int>::max();
        if(result * sign < numeric_limits<int>::min()) return numeric_limits<int>::min();
    }


    // 5. Range check and clamping
    result *= sign;
    if (result > numeric_limits<int>::max()) {
        return numeric_limits<int>::max();
    } else if (result < numeric_limits<int>::min()) {
        return numeric_limits<int>::min();
    } else {
        return (int)result;
    }
}

int main() {
    string s1 = "42";
    string s2 = "   -42";
    string s3 = "4193 with words";
    string s4 = "words and 987";
    string s5 = "-91283472332";
    string s6 = "+-12";
    string s7 = "  00000-42a1234";
    string s8 = "2147483648";
    string s9 = "-2147483649";

    cout << "Atoi of '" << s1 << "' is: " << myAtoi(s1) << endl; //42
    cout << "Atoi of '" << s2 << "' is: " << myAtoi(s2) << endl; //-42
    cout << "Atoi of '" << s3 << "' is: " << myAtoi(s3) << endl; //4193
    cout << "Atoi of '" << s4 << "' is: " << myAtoi(s4) << endl; //0
    cout << "Atoi of '" << s5 << "' is: " << myAtoi(s5) << endl; //-2147483648
    cout << "Atoi of '" << s6 << "' is: " << myAtoi(s6) << endl; //0
    cout << "Atoi of '" << s7 << "' is: " << myAtoi(s7) << endl; //0
    cout << "Atoi of '" << s8 << "' is: " << myAtoi(s8) << endl; //2147483647
    cout << "Atoi of '" << s9 << "' is: " << myAtoi(s9) << endl; //-2147483648

    return 0;
}

Complexity

• Time Complexity: O(n), where n is the length of the input string. We iterate through the string at most once.
• Space Complexity: O(1). We use a constant amount of extra space.