My O(n) C++ Solution with Finite state machine


  • 0
    B
    class Solution {
    public:
        int atoi(const char *str) {
            if (str == NULL)
                return 0;
            int sum = 0;
            bool is_negative = false;
            int state = 0;
            // beg and end is dight char range
            int beg = 0, end = 0;
            int i = 0;
            for(; str[i] != '\0'; i++) {
                if (state == 0) {
                    // when state is 0
                    // we skip white space
                    if (str[i] == '-') {
                        is_negative = true;
                        beg = i;
                        state = 1;
                    } else if (str[i] == '+') {
                        is_negative = false;
                        beg = i;
                        state = 1;
                    } else if (str[i] == ' ') {
                        continue;
                    } else if (str[i] > '0' && str[i] <= '9') {
                        beg = i;
                        char ch = str[i];
                        int cur = ch - '0';
                        sum = cur + sum * 10;
                        state = 2;
                    } else if (str[i] == '0') {
                        beg = i;
                        state = 1;
                    } else {
                        return 0;
                    }
                } else if (state == 1) {
                    // filter zero before digit
                    // we find first dight char greater than 0
                    if (str[i] == '0') {
                        continue;
                    } else if (str[i] > '0' && str[i] <= '9') {
                        beg = i;
                        char ch = str[i];
                        int cur = ch - '0';
                        sum = cur + sum * 10;
                        state = 2;
                    } else {
                        return 0;
                    }
                }
                else {
                    // when state is 2
                    // we are in digit range, we need to check the end of str
                    if (str[i] >= '0' && str[i] <= '9') {
                        char ch = str[i];
                        int cur = ch - '0';
                        sum = cur + sum * 10;
                    } else {
                        break;
                    }
                }
            }
            end = i;
            
            if (is_negative) {
                // check underflow
                if (underflow(str, beg, end))
                    return -2147483648;
                else
                    return -sum;
            } else {
                // check overflow
                if (overflow(str, beg, end))
                    return 2147483647;
                else
                    return sum;
            }
        }
        
        bool overflow(const char *str, int beg, int end) {
            const char *max_int = "2147483647";
            const int length = 10;
            if ((end - beg) > length) {
                return true;
            } else if ((end - beg) < length) {
                return false;
            } else {
                // same length
                // compare part of str to max_int
                for (int i = 0; i < length; i++) {
                    if (str[beg + i] > max_int[i])
                        return true;
                    if ((str[beg + i] < max_int[i]))
                        return false;
                }
                return false;
            }
        }
        
        bool underflow(const char *str, int beg, int end) {
            const char *max_int = "2147483648";
            const int length = 10;
            if ((end - beg) > length) {
                return true;
            } else if ((end - beg) < length) {
                return false;
            } else {
                // same length
                // compare part of str to max_int
                for (int i = 0; i < length; i++) {
                    if (str[beg + i] > max_int[i])
                        return true;
                    if ((str[beg + i] < max_int[i]))
                        return false;
                }
                return false;
            }
        }
    };

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.