Thursday, January 8, 2015

String to Integer (atoi) (LeetCode Math)

Question: 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.

Idea: We need to handle a few special cases,
1) possible empty spaces before and after the digits.
Solved by: trim()
2) possible '+' or the '-' symbol in the front of the digits.
Solved by: check the first symbol
3) possible overflow if bigger than Integer.MAX_VALUE or smaller than Integer.MIN_VALUE.
Solved by: Use a long type variable to cache the result, whenever the partial result is out of the boundary (max_value, min_value), stop and return. Otherwise the result may even overflow in long type......

Time: O(n) Space: O(1)

Code:
 public class Solution {  
   public int atoi(String str) {  
     str=str.trim();  
     if(str.length()==0)  
       return 0;  
     int sign=1;  
     int index=0;  
     if(str.charAt(index)=='+')  
     {  
       sign=1;  
       index++;  
     }  
     else if(str.charAt(index)=='-')  
     {  
       sign=-1;  
       index++;  
     }  
     long num=0;  
     while(index<str.length())  
     {  
       if(str.charAt(index)<'0'||str.charAt(index)>'9')  
         break;  
       num=num*10+(int)(str.charAt(index)-'0');  
       if(num*sign>Integer.MAX_VALUE||num*sign<Integer.MIN_VALUE)  
         break;  
       index++;  
     }  
     if(sign*num>Integer.MAX_VALUE)  
       return Integer.MAX_VALUE;  
     if(sign*num<Integer.MIN_VALUE)  
       return Integer.MIN_VALUE;  
     return (int)(sign*num);  
   }  
 }  

No comments:

Post a Comment