all articles

# leetcode war 8 - String to Integer (atoi)

2016-10-10

https://leetcode.com/problems/string-to-integer-atoi/

Implement atoi to convert a string to an integer.

Hint: Carefully consider all possible input cases. If you want a challenge, please do not see below and ask yourself what are the possible input cases.

Notes: It is intended for this problem to be specified vaguely (ie, no given input specs). You are responsible to gather all the input requirements up front.

# analysis

Firstly we have to list up all the possible forms of an integer(in C), what I can think of is:

example desc
`"120"`, `"+120"` decimal integer
`"-120"` negative integer
`"0x120"` `"0X120"` hexadecimal integer
`"0120"` octal integer

and there are also postfix that needs attention.

post fix desc
`u`, `U` unsigned number,
`l`, `L` long int, which use 4 bytes, without l , integers use only 2 bytes.

based on the postfix above, numbers maybe overflowed, we should return what ? 0 ?

For those strings that cannot be converted, we return 0;

We just traverse the string, and do the calculation at the same time.

# Coding

``````var myAtoi = function(str) {
var result = 0;
var sign  = 1;
var countOfSign = 0;
var i = 0;
var char = null;
var base = 10;

char = str[i];
if (char === '+' || char === '-'){
countOfSign++;
if (char === '-'){
sign = -1;
}
} else if (char >= '0' || char <= '9'){
if (char === '0'){
base = 8;
}
result = result * base + (char - '0');
} else {
return result;
}

i++;

while (i < str.length){
char = str[i];
if (i - countOfSign === 0 && char === '0'){
base = 8;
} else if (i - countOfSign === 1 && (char === 'x' || char === 'X')){
base = 16;
} else if (char >= '0' || char <= '9'){
result = result * base + (char - '0');
} else {
break;
}
i++;
}
return result * sign;
};
``````

Above one get right result but misses handling of postfix-`l`, and `u`, let's fix that.

When `l` or `u` are encountered, update the max & min;

``````/**
* @param {string} str
* @return {number}
*/
var myAtoi = function(str) {
var result = 0;
var sign  = 1;
var countOfSign = 0;
var i = 0;
var char = null;
var base = 10;
var isUnsigned = false;
var isLong = false;

var MAX_INT = Math.pow(2, 15) - 1;
var MIN_INT = -Math.pow(2, 15);

char = str[i];
if (char === '+' || char === '-'){
countOfSign++;
if (char === '-'){
sign = -1;
}
} else if (char >= '0' && char <= '9'){
if (char === '0'){
base = 8;
}
result = result * base + (char - '0');
} else {
return result;
}

i++;

while (i < str.length){
char = str[i];
if (i - countOfSign === 0 && char === '0'){
base = 8;
} else if (i - countOfSign === 1 && (char === 'x' || char === 'X')){
base = 16;
} else if (char >= '0' && char <= '9'){
result = result * base + (char - '0');
} else if ((char === 'u' || char === 'U') && !isUnsigned){
isUnsigned = true;
} else if ((char === 'l' || char === 'L') && !isLong){
isLong = true;
} else {
break;
}
i++;
}

if (isLong){
MAX_INT = Math.pow(2, 31) - 1;
MIN_INT = -Math.pow(2, 31);
}

if (isUnsigned){
if (sign === -1){
return 0;
}

MAX_INT = MAX_INT - MIN_INT;
MIN_INT = 0;
}

result = result * sign;
if (result < MIN_INT || result > MAX_INT){
return 0;
} else {
return result;
}
};

console.assert(myAtoi("011") === 9);
console.assert(myAtoi("-011") === -9);
console.assert(myAtoi("0") === 0);
console.assert(myAtoi("11") === 11);
console.assert(myAtoi("-11") === -11);
console.assert(myAtoi("0x11") === 17);
console.assert(myAtoi("-0x11") === -17);
console.assert(myAtoi("32767") === 32767);
console.assert(myAtoi("32768") === 0);
console.assert(myAtoi("32768u") === 32768);
console.assert(myAtoi("32768l") === 32768);
console.assert(myAtoi("32768l") === 32768);``````

But it failed passing leetcode, seems that my understanding of the problem is wrong.

# Case By Case debugging

1. for `"010"`, 10 is expected, by we offer think it as octal 8. which means we don't consider octal thing.
2. for `" 010"`, 10 is expected, so we needs to skip white space;
3. for `"+-2"`, 0 is expected.
4. for `"2147483648"` , `2147483647` is expected, so return MAX/MIN when overflowed rather than 0.
``````var myAtoi = function(str) {
var result = 0;
var sign  = 1;
var i = 0;
var char = null;
var base = 10;
var isStarted = false;

var MAX_INT = Math.pow(2, 31) - 1;
var MIN_INT = -Math.pow(2, 31);

while (i < str.length){
char = str[i];
if ((char >= '0' && char <= '9')){
isStarted = true;
result = result * base + (char - '0');
} else if ((char === '+' || char === '-') && !isStarted){
isStarted = true;
if (char === '-'){
sign = -1;
}
} else if (!(char === ' ' && !isStarted)){
break;
}
i++;
}

return Math.min(Math.max(result * sign, MIN_INT), MAX_INT);
};``````

It passed at 135ms, top 40% out of javascript submission.

Honestly, this is not a very much algorithm problem I think. 