algoadvance

Leetcode 8. String to Integer (atoi)

Problem Statement

The task is to implement the myAtoi(string s) function, which converts a string to a 32-bit signed integer (similar to C/C++’s atoi function).

The function first discards as many whitespace characters as necessary until the first non-whitespace character is found. Then, starting from this character, takes an optional initial plus (+) or minus (-) sign followed by as many numerical digits as possible, and interprets them as a numerical value.

The string can contain additional characters after those that form the integral number, which are ignored and have no effect on the behavior of this function.

If the first sequence of non-whitespace characters in s is not a valid integral number, or if no such sequence exists because the string is empty or contains only whitespace characters, no conversion is performed.

If no valid conversion could be performed, a zero value is returned.

If the numerical value is out of the range of a 32-bit signed integer, then:

• Return INT_MAX (2147483647) if the value is positive.
• Return INT_MIN (-2147483648) if the value is negative.

Clarifying Questions

1. Should I handle leading whitespace in the input string?
   • Yes, leading whitespaces should be discarded.
2. Should I stop reading the string as soon as an invalid character is encountered?
   • Yes, you should stop parsing as soon as any character other than numerical digits, or a sign after leading whitespace, is encountered.
3. If the string represents a value outside the 32-bit signed integer range, what should I return?
   • Return INT_MAX or INT_MIN depending on the sign of the number.

Strategy

1. Skip leading whitespaces.
2. Check if the next character is a + or - to determine the sign, otherwise assume it’s a positive number.
3. Convert subsequent numerical characters to an integer until an invalid character is encountered or the end of the string is reached.
4. Handle overflow by returning INT_MAX or INT_MIN if necessary.

Code

#include <string>
#include <climits>

class Solution {
public:
    int myAtoi(std::string s) {
        int i = 0;
        int n = s.size();
        
        // Step 1: Ignore leading whitespaces
        while (i < n && s[i] == ' ') {
            i++;
        }
        
        // Step 2: Check if the next character is '+' or '-'
        int sign = 1;
        if (i < n && (s[i] == '+' || s[i] == '-')) {
            sign = (s[i] == '-') ? -1 : 1;
            i++;
        }
        
        // Step 3: Convert subsequent numerical characters to integer
        long long result = 0;
        while (i < n && isdigit(s[i])) {
            result = result * 10 + (s[i] - '0');
            
            // Step 4: Handle overflow
            if (result * sign > INT_MAX) return INT_MAX;
            if (result * sign < INT_MIN) return INT_MIN;
            
            i++;
        }
        
        return static_cast<int>(result * sign);
    }
};

Time Complexity

• The time complexity is O(n), where n is the number of characters in the string. In the worst case, we traverse the string once.

Space Complexity

• The space complexity is O(1) since we use only a constant amount of extra space for variables.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?