Problem

Implement the myAtoi(string s) function, which converts a string to a 32-bit signed integer.

The algorithm for myAtoi(string s) is as follows:

  1. Whitespace: Ignore any leading whitespace (" ").
  2. Signedness: Determine the sign by checking if the next character is '-' or '+', assuming positivity is neither present.
  3. Conversion: Read the integer by skipping leading zeros until a non-digit character is encountered or the end of the string is reached. If no digits were read, then the result is 0.
  4. Rounding: If the integer is out of the 32-bit signed integer range [-2^31, 2^31 - 1], then round the integer to remain in the range. Specifically, integers less than -2^31 should be rounded to -2^31, and integers greater than 2^31 - 1 should be rounded to 2^31 - 1.

Return the integer as the final result.

Examples

Example 1:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

Input: s = "42"
Output: 42

Explanation:
The underlined characters are what is read in and the caret is the current reader position.
Step 1: "42" (no characters read because there is no leading whitespace)
         ^
Step 2: "42" (no characters read because there is neither a '-' nor '+')
         ^
Step 3: "42" ("42" is read in)

Some Important Points and Questions Before Coding

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.

Q1. Does string contain whitespace characters before the number? A. Yes Q2. Can the string have garbage characters after the number? A. Yes. Ignore it. Q3. If no numeric character is found before encountering garbage characters, what should I do? A. Return 0. Q4. What if the integer overflows? A. Return INT_MAX if the number is positive, INT_MIN otherwise. Warning : DO NOT USE LIBRARY FUNCTION FOR ATOI. If you do, we will disqualify your submission retroactively and give you penalty points.

Solution

The following cases should be considered for this problem:

1
2
3
4
5

1. null or empty string
2. white spaces
3. +/- sign
4. calculate real value
5. handle min & max

Method 1 - String Iteration

Here are the steps we can follow:

  • Step 1: The string is trimmed to remove any leading whitespace.
  • Step 2: If there is a sign character ('-' or '+'), the sign is recorded, and the index is incremented.
  • Step 3: The characters are converted to integers until a non-digit character is encountered or the end of the string is reached.
  • Step 4: During conversion, the algorithm checks for overflow and adjusts the result to stay within the 32-bit signed integer limits, returning Integer.MAX_VALUE or Integer.MIN_VALUE if necessary. Finally, the sign is applied to the result.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47

public class Solution {

	public int myAtoi(String s) {
		// Step 1: Ignore leading whitespace
		s = s.trim();

		if (s.isEmpty()) {
			return 0;
		}

		int sign = 1; // the assumption of positivity
		int index = 0; // to traverse each character in the string
		int result = 0;
		int n = s.length();
		int INT_MAX = Integer.MAX_VALUE;
		int INT_MIN = Integer.MIN_VALUE;

		// Step 2: Check for sign
		if (s.charAt(index) == '+') {
			index++;
		} else if (s.charAt(index) == '-') {
			sign = -1;
			index++;
		}

		// Step 3: Conversion
		while (index < n) {
			char c = s.charAt(index);

			if (!Character.isDigit(c)) {
				break;
			}

			int digit = c - '0';

			// Step 4: Rounding
			if (result > (INT_MAX - digit) / 10) { // handle overflow
				return sign == 1 ? INT_MAX : INT_MIN;
			}

			result = result * 10 + digit;
			index++;
		}

		return result * sign; // apply sign at the end
	}
}

Complexity

  • ⏰ Time complexity: O(n) where n is the length of the string.
  • 🧺 Space complexity: O(1)