[leetcode] 8. String to Integer (atoi)

Table of Contents

Description

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 positive if 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 are 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.

Example 1:

Input: s = "42"
Output: 42

Explanation:
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)

Example 2:

Input: s = " -042"
Output: -42

Explanation:
Step 1: " -042" (leading whitespace is ignored)
Step 2: " -042" (- is read, so the result should be negative)
Step 3: " -042" (“042” is read in, leading zeroes are ignored in the result)

Example 3:

Input: s = "1337c0d3"
Output: 1337

Explanation:
Step 1: "1337c0d3" (no characters read because there is no leading whitespace)
Step 2: "1337c0d3" (no characters read because there is neither a - nor +)
Step 3: "1337c0d3" (“1337” is read in; reading stops because the next character is a non-digit)

Example 4:

Input: s = "0-1"
Output: 0

Explanation:
Step 1: "0-1" (no characters read because there is no leading whitespace)
Step 2: "0-1" (no characters read because there is neither a - nor +)
Step 3: "0-1" (“0” is read in; reading stops because the next character is a non-digit)

Example 5:

Input: s = "words and 987"
Output: 0

Explanation:
Reading stops at the first non-digit character 'w'.

Constraints:

• $0 <= s.length <= 200$
• s consists of English letters (lower-case and upper-case), digits, ' ', '+', '-', and '.'.

Approach

Walk through each character of the string and convert the string into numbers according to the steps outlined in the problem.

1. Remove leading whitespace.
2. Determine the sign.
3. Read the integer.

Solution

/**
 * @param {string} s
 * @return {number}
 */
var myAtoi = function (s) {
  const MAX_INT = Math.pow(2, 31) - 1;
  // Calculate the threshold to check for overflow before multiplying by 10
  const OVERFLOW_THRESHOLD = Math.floor(MAX_INT / 10);
  const WHITE_SPACE = " ";
  const PLUS_SIGN = "+";
  const MINUS_SIGN = "-";
  let i = 0,
    sign = 1,
    result = 0;

  // Remove leading whitespaces
  while (s[i] === WHITE_SPACE) {
    i++;
  }

  // Check for a sign character and update the sign variable accordingly
  if ([PLUS_SIGN, MINUS_SIGN].includes(s[i])) {
    if (s[i] === MINUS_SIGN) sign = -1;
    i++;
  }

  // Process numerical digits and construct the integer
  while (s[i] >= "0" && s[i] <= "9") {
    const digit = Number(s[i]);

    // Check for overflow
    if (result > OVERFLOW_THRESHOLD || MAX_INT - result * 10 < digit) {
      result = sign > 0 ? MAX_INT : MAX_INT + 1;
      break;
    } else {
      // Update result by adding the current digit in underflow conditions
      result = result * 10 + digit;
    }
    i++;
  }

  // Return the final computed integer with the correct sign
  return result * sign;
};

Complexity Analysis

Time Complexity

The time complexity is $O(n)$, where $n$ is the length of the input string s.

Space Complexity

The space complexity is $O(1)$ because we use a constant amount of space.