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

• ``````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;
}
}
};``````

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