String To Integer Atoi - Leetcode Solution

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

The algorithm should do the following:

1. Ignore initial white spaces
2. Check for an optional sign (+/-)
3. Read in digits until the next non-digit character
4. Convert the digits to an integer, and return the integer value.

If the algorithm cannot perform the conversion, it returns 0.

Function Signature: int myAtoi(string s)

Solution:

We will follow the steps as given in the problem statement:

1. Ignore initial white spaces: We loop until we encounter a non-white space character.
2. Check for an optional sign (+/-): If we encounter a '-' sign, we set the 'negative' flag. If we encounter a '+' sign or no sign, we leave the 'negative' flag unset.
3. Read in digits until the next non-digit character: We loop through the input until we encounter a non-digit character. We keep track of the sum of digits accumulated so far by multiplying the earlier sum by 10 and adding the value of the current digit to the result.
4. Convert the digits to an integer, and return the integer value: We return the integer value after applying the sign.

Note that we also need to make sure that the value does not overflow the 32-bit signed integer range [-2^31,2^31 - 1].

Code:

class Solution { public: int myAtoi(string s) { int i = 0, n = s.size(), sign = 1; long long int res = 0; // Step 1: Ignore initial white spaces while (i < n && s[i] == ' ') i++; // Step 2: Check for an optional sign (+/-) if (i < n && s[i] == '-') { sign = -1; i++; } else if (i < n && s[i] == '+') { i++; } // Step 3: Read in digits until the next non-digit character while (i < n && isdigit(s[i])) { res = res * 10 + s[i] - '0'; i++; if (res > INT_MAX) // check for overflow return (sign == -1) ? INT_MIN : INT_MAX; } // Step 4: Convert the digits to an integer, and return the integer value return sign * res; } };

Time Complexity: O(n), where n is the length of the input string. Space Complexity: O(1). We use constant extra space.

1