008. String to Integer (atoi)

Difficulty: Easy

Frequency: High

Implement atoi to convert a string to an integer.
Requirements for atoi: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 str is not a valid integral number, or if no such sequence exists because either str is empty or it contains only whitespace characters, no conversion is performed.

If no valid conversion could be performed, a zero value is returned. If the correct value is out of the range of representable values, INT_MAX (2147483647) or INT_MIN (-2147483648) is returned.


My solution:
Data structure:
string
Steps:
Loop through the string
1. Decide whether it is positive or negative
2. Find the all the digits
3. If the result > MAX or result < MIN, return MAX or MIN
4. stop when encounter non-digit
 
Complexity:
Runtime: O(n)
Space: O(n)
Test cases:
24980
+24980
-24980
Corner cases:
1. empty string: ” “
2. no digit in string: sda
3. digit and other characters mixed: +54ab8, ft-50a
4. leading or trailing space
4. INT_MAX(2147483647) and INT_MIN(-2147483648)
Code:
class Solution {
public:
    int myAtoi(string str) {
        long result = 0;
        bool negative = false;
        bool valid = false;
        for (int i = 0; i &lt; str.size(); i++) {
            if (isspace(str[i]) &amp;&amp; !valid) {
                continue;
            } else if (str[i] == '-' &amp;&amp; !valid) {
                negative = true;
                valid = true;
            } else if (str[i] == '+' &amp;&amp; !valid) {
                valid = true;
            } else if (isdigit(str[i])) {
                valid = true;
                result = result * 10 + (str[i] - 48);
                if (!negative &amp;&amp; result &gt; INT_MAX) {
                    return INT_MAX;
                } else if (negative &amp;&amp; -result &lt; INT_MIN) {
                     return INT_MIN;
                }
            } else {
                break;
            }
        }
        return (int)(negative? -result: result);
    }
};

Another solution:
Data structure:
string
Steps:
1. Find the first non-space character
2. Decide the sign
Complexity:
Runtime: O(n)
Space: O(n)
Code:
class Solution {
public:
    int myAtoi(string str) {
        int ret = 0, sign = 1, i = str.find_first_not_of(' '), base = INT_MAX / 10;
        if (str[i] == '+' || str[i] == '-')
            sign = str[i++] == '+' ?: -1;
        while (isdigit(str[i])) {
            if (ret &gt; base || (ret == base &amp;&amp; str[i] - '0' &gt; INT_MAX%10))
                return sign &gt; 0 ? INT_MAX : INT_MIN;
            ret = 10 * ret + (str[i++] - '0');
        }
        return sign * ret;
    }
};

Things to learn:
1. using int sign = 1, not bool negative = false;
2. how to handle overflow in conversion
3. using c++ function to simplify code/logic, ex: find_first_not_of
4. convert char to int: -‘0’
5. conditional operator: default is 1 for the first result
Advertisements

2 thoughts on “008. String to Integer (atoi)

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s