Tuesday, February 11, 2014

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.
Solution:
The key for this question is the corner cases:
1. space at the beginning of string.
2. sign bit before numbers.
3. overflow, since there is no string length limit.

public class Solution {
    public int atoi(String str) {
        int len = str.length();
        if(len == 0) return 0;
        int i = 0;
        boolean sign =  true;
        
        while(str.charAt(i) == ' ') i++;
        
        if(str.charAt(i) == '+' || str.charAt(i) == '-'){
            if(str.charAt(i) == '-'){
                sign = false;   
            }
            i++;
        }
        int ret = 0;
        for(; i < len; i++){
            int tmp = str.charAt(i) - '0';
            if(tmp < 0 || tmp > 9) break;
            
            //ret * 10 + tmp should be smaller than MAX_VALUE;Otherwise it may overflow
            if(ret > Integer.MAX_VALUE / 10 || 
               (ret == Integer.MAX_VALUE / 10 && tmp > Integer.MAX_VALUE % 10)){   
                return sign == true ? Integer.MAX_VALUE : Integer.MIN_VALUE;
            }
            
            ret = ret * 10 + tmp;
        }
        return sign == true ? ret : -ret;
    }
}

No comments:

Post a Comment