8.md

8. String to Integer (atoi)

Description

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.

Thinking Process

1. If the char isn't numeric:
   1. If sign has been set -> return result * sign
   2. If sign hasn't been set -> skip if char is ' ', or set the sign, or terminate the program
2. If the char is numeric:
   1. Set the signSet to be true
   2. Check for potential overflow, terminate the program if needed
   3. If no overflow, update the result
3. Return the result * sign to get converted integer value

public int myAtoi(String str) {
    int result = 0;
    int sign = 1;
    boolean signSet = false;
    
    for(int i=0; i < str.length(); i++){
        char c = str.charAt(i);
        if(!Character.isDigit(c)){
            if(signSet)
                return result * sign;
            else{
                if(c == ' ')
                    continue;
                if(c == '+'){
                    signSet = true;
                    continue;
                }
                if(c == '-'){
                    signSet = true;
                    sign = -1;
                    continue;
                }
                return result * sign;
            }
        }
        else{
            signSet = true;
            if((Integer.MAX_VALUE - Character.getNumericValue(c)) / 10 < result)
                if(sign == 1)
                    return Integer.MAX_VALUE;
                else
                    return Integer.MIN_VALUE;
            result = result * 10 + Character.getNumericValue(c);
        }
    }
    return result * sign;
}

Complexity

1. O(n) in time by scanning through the string

Trick

• Separate the sign from the result makes it easier to do overflow checking (only need to check overflowing the Integer.MAX_VALUE)