Leetcode: String to Integer

Datetime:2016-08-23 01:20:48          Topic: LeetCode           Share

Problem

Leetcode link

Implement atoi to convert a string to an integer.

Analyze

This is the previous answer to this question

The complexity of this problem is how to handle edge cases.

For int, standard as 32-bit length, has a max value of (1<<31) - 1 and a min value of (1<<31) .

When read each digit from string, need check if the result will be overflow.

And another situation is that the leading blank spaces, and possibly has + or - .

Code

class Solution {
public:
    const int max = (1<<31) - 1;
    const int min = -max - 1;

    inline bool willOverflow(int sign, int base, int digit) {
        static const int maxTenth = max / 10;
        static const int maxDigit = max % 10;
        static const int minTenth = - (min / 10);
        static const int minDigit = - (min % 10);
        if(sign == 1){
            return (base > maxTenth || base == maxTenth && digit > maxDigit);
        } else {
            return (base > minTenth || base == minTenth && digit > minDigit);
        }
    }

    // The test case only allow "    -123" like this, after hit sign or digit, can not take any invalid or blank char.
    int myAtoi(string str) {
        if (str.size() == 0) return 0;
        int sign = 1;
        bool gotNumber = false; //allow blank space before number
        bool gotSign = false; // allow <= 1 sign
        int result = 0;
        for(int i = 0; i < str.size(); ++i) {
            if(!gotNumber && str[i] == ' ') continue; 
            if(!gotNumber && !gotSign && (str[i] == '+' || str[i] == '-')){
                sign = str[i]=='-' ? -1 : 1;
                gotSign = true;
                gotNumber = true;
                continue;
            }
            if(str[i] < '0' || str[i] > '9')
                return result * sign;
            gotNumber = true;
            int digit = str[i] - '0';
            if(willOverflow(sign, result, digit))
                return sign == 1 ? max : min;
            result = result * 10 + digit;
        }
        return result * sign;
    }
};




About List