Leetcode – 8 – String to Integer (atoi)

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.

Description:

In this problem we have to convert the string given into Integers. The challenge here is to get all the test cases right.

So first we will list all the test cases and make sure what is expected

  • Check for null or “” string
  • Check for Negative sign (-) (–) (-+) (abc+123-123)
  • Check for Positive sign (+) consider (++), (+-) (abc123-123+123)
  • Check for decimal (.)
  • Check for comma separated (,)
  • Check for Overflow and Underflow
  • Check for spaces ( ab133) (123  34) (  1223) (   000123) (    + 123)  (   –+123)
  • Check for 0 in from of number (000123) (-000123)
  • Check for special characters ($123,#123)

Efficient solution: (Using ASCII, Modulo and charAt)

To determine the character we tend to use ASCII character and map to the number corresponding to it. The ascii value for 0 to 9 is 48 to 57.  We will make use of this in our logic.

  • trim the string to omit all leading or trailing spaces
  • check for the sign of the number ‘+’ or ‘-‘
  • Get the character and compare it with the ascii value and determine the number
  • Check for overflow & underflow

1

Code:

public class Solution {
public int myAtoi(String str) {
    if(str==null||str.length()==0){
        return 0;
    }
    str=str.trim();
    int n =str.length();
    int sign =1;
    int res=0;
    for(int i=0;i<n;i++){
        char ch =  str.charAt(i);
        if(ch =='+'|| ch =='-'){
            if(i==0){
                sign=ch=='+'?1:-1;
            }
            else{
                return sign*res;
            }
        }
        else if(ch =='.'){
            return sign*res;
        }
        else if(!Character.isDigit(ch)){
            return sign*res;
        }
        else{
            int charnum =Integer.parseInt(ch+"");
            int temp = res*10+charnum;
            if(res>=Integer.MAX_VALUE/10&&charnum>=8||(temp-charnum)/10!=res){
                return sign==1?Integer.MAX_VALUE:Integer.MIN_VALUE;
            }
            res=temp;
        }
    }
    return sign*res;
}
}

Time Complexity: O(n)

  • Loop through the digits upto n – O(n)

Space Complexity: O(1)

  • We will store the values in the result – O(1)

Available Test Cases: 1047

  • Check for null or “” string
  • Check for Negative sign (-) (–) (-+) (abc+123-123)
  • Check for Positive sign (+) consider (++), (+-) (abc123-123+123)
  • Check for decimal (.)
  • Check for comma separated (,)
  • Check for Overflow and Underflow
  • Check for spaces ( ab133) (123  34) (  1223) (   000123) (    + 123)  (   –+123)
  • Check for 0 in from of number (000123) (-000123)
  • Check for special characters ($123,#123)

 Github:

Leetcode_8_String_to_Integer

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: