It is another gloomy day in the Twin Cities of Minneapolis and St. Paul. So far is has been raining on and off. The temperature has risen to the mid to upper 50’s. We are still in April so not much to complaint about yet.
I am working on a set of problems at LeetCode. Some I have already solved while others not. In the case of LeetCode 8 String to Integer (atoi) I had solved it as you can see here.
At the time the answer was good enough so I left it there. Since I am giving myself a second chance, I decided to work on a third implementation of the required function.
Implement atoi which converts a string to an integer. The function first discards as many whitespace characters as necessary until the first non-whitespace character is found. Then, starting from this character, takes an optional initial plus or minus sign followed by as many numerical digits as possible, and interprets them as a numerical value. The string can contain additional characters after those that form the integral number, which are ignored and have no effect on the behavior of this function. If the first sequence of non-whitespace characters in str is not a valid integral number, or if no such sequence exists because either str is empty or it contains only whitespace characters, no conversion is performed. If no valid conversion could be performed, a zero value is returned. Note: Only the space character ' ' is considered as whitespace character. Assume we are dealing with an environment which could only store integers within the 32-bit signed integer range: [−231, 231 − 1]. If the numerical value is out of the range of representable values, INT_MAX (231 − 1) or INT_MIN (−231) is returned.
The problem is very well defined especially if you work with C / C++. The idea is to parse a string and return the associated integer. We are going to solve the problem using Java and the VSCode IDE on a Windows 10 computer.
Please read the current description at the LeetCode site and get the current requirements. They might have been edited since I addressed this problem.
42 main <<< str ==>42<== main <<< myAtoi0: 42 main <<< myAtoi1: 42 main <<< myAtoi: 42 -42 main <<< str ==> -42<== main <<< myAtoi0: -42 main <<< myAtoi1: -42 main <<< myAtoi: -42 4193 with words main <<< str ==>4193 with words<== main <<< myAtoi0: 4193 main <<< myAtoi1: 4193 main <<< myAtoi: 4193 words and 987 main <<< str ==>words and 987<== main <<< myAtoi0: 0 main <<< myAtoi1: 0 main <<< myAtoi: 0 123abc main <<< str ==>123abc<== main <<< myAtoi0: 123 main <<< myAtoi1: 123 main <<< myAtoi: 123 abc123 main <<< str ==>abc123<== main <<< myAtoi0: 0 main <<< myAtoi1: 0 main <<< myAtoi: 0 3.14159 main <<< str ==>3.14159<== main <<< myAtoi0: 3 main <<< myAtoi1: 3 main <<< myAtoi: 3 -91283472332 main <<< str ==>-91283472332<== main <<< myAtoi0: -2147483648 main <<< myAtoi1: -2147483648 main <<< myAtoi: -2147483648 12345678901234567890 main <<< str ==>12345678901234567890<== main <<< myAtoi0: 2147483647 main <<< myAtoi1: 2147483647 main <<< myAtoi: 2147483647 main <<< str ==><== main <<< myAtoi0: 0 main <<< myAtoi1: 0 main <<< myAtoi: 0 + main <<< str ==>+<== main <<< myAtoi0: 0 main <<< myAtoi1: 0 main <<< myAtoi: 0 - main <<< str ==>-<== main <<< myAtoi0: 0 main <<< myAtoi1: 0 main <<< myAtoi: 0 +-2 main <<< str ==>+-2<== main <<< myAtoi0: 0 main <<< myAtoi1: 0 main <<< myAtoi: 0 - 234 main <<< str ==>- 234<== main <<< myAtoi0: 0 main <<< myAtoi1: 0 main <<< myAtoi: 0 1234 main <<< str ==>1234<== main <<< myAtoi0: 1234 main <<< myAtoi1: 1234 main <<< myAtoi: 1234 main <<< str ==> <== main <<< myAtoi0: 0 main <<< myAtoi1: 0 main <<< myAtoi: 0 -42 main <<< str ==> -42<== main <<< myAtoi0: -42 main <<< myAtoi1: -42 main <<< myAtoi: -42
Our test scaffold read the first line which represents a string which we need to use to get the associated integer.
The second line displays the value our test code has read in.
As you can see this time we will call three different implementations. In the previous post we just called the first two.
Note that all implementations return the same answer. That gives us a warm and fuzzy feeling that we might be doing things right. That said, you must submit tour answer to LeetCode since they provide a large number of test cases.
/**
* Test scaffolding.
*/
public static void main(String[] args) {
// **** open scanner ****
Scanner sc = new Scanner(System.in);
// **** read the string ****
String str = sc.nextLine();
// **** close scanner ****
sc.close();
// **** display the string ****
System.out.println("main <<< str ==>" + str + "<==");
// **** convert string to integer (if possible) and display value ****
System.out.println("main <<< myAtoi0: " + myAtoi0(str));
// **** convert string to integer (if possible) and display value ****
System.out.println("main <<< myAtoi1: " + myAtoi1(str));
// **** convert string to integer (if possible) and display value ****
System.out.println("main <<< myAtoi: " + myAtoi(str));
}
Our test scaffold is quite simple and matches the description we provided while describing the screen capture of several tests.
/**
* Flags if an integer is positive or negative.
*/
enum SIGN {
POS, NEG, UNKNOWN
}
For the first and probably second implementations I used the SIGN definition. On the third implementation I just went with a 1 or a -1 to indicate positive or negative result respectively.
/**
* Implement atoi which converts a string to an integer.
*
* Runtime: 4 ms, faster than 18.46% of Java online submissions.
* Memory Usage: 39 MB, less than 38.01% of Java online submissions.
*/
static int myAtoi1(String str) {
// **** list of digits ****
String digits = "0123456789";
// **** value to be returned ****
int result = 0;
// **** remove leading and trailing spaces ****
str = str.trim();
// **** sanity check ****
if (str.equals("") || str.equals("+") | str.equals("-"))
return 0;
// **** positive sign****
SIGN sign = SIGN.POS;
// **** check for leading sign ****
if ((str.charAt(0) == '-') || (str.charAt(0) == '+')) {
// **** negative value ****
if (str.charAt(0) == '-')
sign = SIGN.NEG;
// **** skip leading sign ****
str = str.substring(1);
// **** check if we have an empty string ****
if (str.equals(""))
return 0;
}
// **** split ****
String[] words = str.split(" ");
// **** for ease of use ****
str = words[0];
// **** check if we have an empty string ****
if (str.equals(""))
return 0;
// **** check if we have something else but digits ****
for (int i = 0; i < str.length(); i++) {
// ***** ****
char ch = str.charAt(i);
// **** check if not a digit ****
if (digits.indexOf(ch, 0) == -1) {
// **** ****
str = str.substring(0, i);
// **** check if we have an empty string ****
if (str.equals(""))
return 0;
// **** ****
break;
}
}
// **** convert the integer string to binary (may throw exception) ****
try {
result = Integer.parseInt(str);
} catch (Exception e) {
if (sign == SIGN.POS)
return Integer.MAX_VALUE;
else
return Integer.MIN_VALUE;
}
// **** return positive or negative result ****
return sign == SIGN.POS ? result : -result;
}
This is the first implementation that we saw in the previous post.
You can see in the comments section the performance of the function.
Also note that on the last few lines we used Integer.parseInt() method to parse the string to a binary. Such approach was accepted by LeetCode.
/**
* Implement atoi which converts a string to an integer.
*
* Runtime: 3 ms, faster than 25.31% of Java online submissions.
* Memory Usage: 38.6 MB, less than 96.38% of Java online submissions.
*/
static int myAtoi0(String str) {
// **** list of digits ****
String digits = "0123456789";
// **** for starters ****
SIGN sign = SIGN.POS;
int result = 0;
// **** remove leading and trailing spaces ****
str = str.trim();
// **** check for blank strings ****
if (str.equals(""))
return 0;
// **** take care of leading sign ****
if ((str.charAt(0) == '-') || (str.charAt(0) == '+')) {
// **** ****
if (str.charAt(0) == '-')
sign = SIGN.NEG;
// **** skip leading sign ****
str = str.substring(1);
}
// **** traverse the string ****
for (int i = 0; i < str.length(); i++) {
// **** get the current character ****
char ch = str.charAt(i);
// **** check if current character is NOT an integer ****
if (digits.indexOf(ch, 0) == -1) {
break;
}
// **** update the result (throws exception) ****
try {
result = Math.multiplyExact(result, 10);
result = Math.addExact(result, ch - '0');
} catch (Exception e) {
if (sign == SIGN.POS)
return Integer.MAX_VALUE;
else
return Integer.MIN_VALUE;
}
}
// **** return positive or negative result ****
return sign == SIGN.POS ? result : -result;
}
This is the second implementation that we saw in the previous post.
You can see in the comments section the performance of the function. Faster than the first pass.
Also note that on the last few lines we do not use the Integer.parseInt() method. We use a couple methods from the Math library.
/**
* Implement atoi which converts a string to an integer.
*
* Runtime: 1 ms, faster than 100.00% of Java online submissions
* Memory Usage: 38.9 MB, less than 65.58% of Java online submissions.
*/
static int myAtoi(String str) {
// **** sanity checks(s) ****
if (str.length() == 0)
return 0;
// **** initialization ****
int i = 0;
int sign = 1;
int result = 0;
// **** discard leading white space(s) ****
while (i < str.length() && str.charAt(i) == ' ')
i++;
// **** check for blank string ****
if (str.length() == 0)
return 0;
// **** assign sign ****
if (i < str.length() && (str.charAt(i) == '+' || str.charAt(i) == '-')){
if (str.charAt(i) == '-') {
sign = -1;
i++;
} else if (str.charAt(i) == '+'){
sign = 1;
i++;
}
}
// **** process digits (compute result) ****
while (i < str.length() && str.charAt(i) >= '0' && str.charAt(i) <= '9') {
// **** check if we overflowed ****
if (result > Integer.MAX_VALUE / 10 ||
(result == Integer.MAX_VALUE / 10 && str.charAt(i) - '0' > Integer.MAX_VALUE % 10)) {
return (sign == 1) ? Integer.MAX_VALUE : Integer.MIN_VALUE;
}
// **** multiply by 10 and add current digit (update result) ****
result = result * 10 + (str.charAt(i++) - '0');
}
// **** return signed result ****
return sign * result;
}
This implementation starts with a sanity check.
After that we initialize three variables. The index ‘i’ is used to track the current character in the input string, the sign for the result which will be represented with 1 for positive and -1 for negative, and the value for the result.
We then skip / discard the leading blank characters in the input string.
If the string is blank, we return 0.
We then assign the sign to the proper variable and skip it in the string.
We now enter a loop processing all consecutive digits in the string. Note that we check if we encounter an overflow or an underflow.
If all is well we just multiply the result by 10 and add the current integer value. This avoid the use of the Integer.parseInt() method.
When all is said and done we return the product of the sign and result variables. Of course if the value overflows or underflows it would be caught inside the last loop.
Check the execution time. It seems to run faster than 100% of previous submissions. Not bad.
Hope you enjoyed solving this problem as much as I did. The entire code for this project can be found in my GitHub repository.
If you have comments or questions regarding this, or any other post in this blog, please do not hesitate and leave me a note below. I will reply as soon as possible.
Keep on reading and experimenting. It is one of the best ways to learn, become proficient, refresh your knowledge and enhance your developer toolset.
Thanks for reading this post, feel free to connect with me John Canessa at LinkedIn.
Regards;
John