String to Integer (atoi)

“String to Integer (atoi)” is a coding problem that requires you to convert a given string to its corresponding integer value. Here’s a more detailed explanation of the problem:

Problem Statement: Implement the atoi function that 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 interpret 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 a whitespace character. Assume we are dealing with an environment that 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, 231 − 1 or −231 is returned.

Example 1:

Input: str = “42” Output: 42

Example 2:

Input: str = ” -42″ Output: -42 Explanation: The first non-whitespace character is ‘-‘, which is the minus sign. Then take as many numerical digits as possible, which gets 42.

Example 3:

Input: str = “4193 with words” Output: 4193 Explanation: Conversion stops at digit ‘3’ as the next character is not a numerical digit.

Example 4:

Input: str = “words and 987” Output: 0 Explanation: The first non-whitespace character is ‘w’, which is not a numerical digit or a +/- sign. Therefore no valid conversion could be performed.

Example 5:

Input: str = “-91283472332” Output: -2147483648 Explanation: The number “-91283472332” is out of the range of a 32-bit signed integer. Therefore, the function returns INT_MIN (−231).

Solution to String to Integer (atoi)

Solution 1: Iterative Approach

In this approach, we iterate over each character of the string and build the integer value by multiplying the current value by 10 and adding the value of the current character. We also keep track of the sign of the number and handle the cases where the string is empty or does not start with a valid character.

Time Complexity: O(n), where n is the length of the string Space Complexity: O(1)

def atoi(s: str) -> int:
    # skip whitespace characters
    i = 0
    while i < len(s) and s[i] == ' ':
        i += 1

    # handle sign of the number
    sign = 1
    if i < len(s) and (s[i] == '+' or s[i] == '-'):
        sign = -1 if s[i] == '-' else 1
        i += 1

    # build the integer value
    result = 0
    while i < len(s) and s[i].isdigit():
        result = result * 10 + int(s[i])
        i += 1

    return max(min(sign * result, 2**31 - 1), -2**31)

Solution 2: Regular Expression Approach

In this approach, we use regular expressions to extract the integer value from the string. We define a regular expression pattern that matches the optional sign character followed by one or more digits. We then use the re module in Python to extract the matching substring and convert it to an integer.

Time Complexity: O(n), where n is the length of the string Space Complexity: O(1)

import re

def atoi(s: str) -> int:
    # define regular expression pattern
    pattern = r'^\s*([-+]?\d+)'

    # find matching substring using regular expression
    match = re.match(pattern, s)

    if match:
        # extract the integer value from the matching substring
        result = int(match.group(1))
        return max(min(result, 2**31 - 1), -2**31)

    return 0

Solution 3: Recursive Approach

In this approach, we recursively build the integer value by first converting the substring starting from the second character (if the first character is a sign) to an integer and then multiplying it by 10 and adding the value of the first character. We also handle the cases where the string is empty or does not start with a valid character.

Time Complexity: O(n), where n is the length of the string Space Complexity: O(n), due to the recursive calls

def atoi(s: str) -> int:
    # handle empty string
    if not s:
        return 0

    # handle sign of the number
    sign = 1
    if s[0] == '+':
        s = s[1:]
    elif s[0] == '-':
        sign = -1
        s = s[1:]

    # recursively build the integer value
    if s and s[0].isdigit():
        return max(min(sign * (ord(s[0]) - ord('0')) + 10 * atoi(s[1:]), 2**31 - 1), -2**31)
    else:
        return 0

An iterative solution is better

Among the three solutions provided earlier, the first solution (Iterative Approach) is the most efficient and preferred solution for the “String to Integer (atoi)” problem. Here’s why:

1. Time Complexity: The time complexity of the Iterative Approach is O(n), where n is the length of the string. This is the same as the time complexity of the other two solutions. However, in practice, the Iterative Approach is faster than the other two solutions since it does not involve any additional overhead of regular expressions or recursive calls.
2. Space Complexity: The space complexity of the Iterative Approach is O(1), which is the best among the three solutions. The other two solutions have a space complexity of O(n) due to the use of regular expressions or recursive calls.
3. Code Clarity: The Iterative Approach is also easier to understand and implement than the other two solutions. It uses simple iteration and basic arithmetic operations to convert the string to an integer.

Therefore, the Iterative Approach is the better solution for the “String to Integer (atoi)” problem due to its faster time complexity, lower space complexity, and simpler implementation.

String to Integer (atoi) Java Solution

public int atoi(String s) {
    // skip whitespace characters
    int i = 0;
    while (i < s.length() && s.charAt(i) == ' ') {
        i++;
    }

    // handle sign of the number
    int sign = 1;
    if (i < s.length() && (s.charAt(i) == '+' || s.charAt(i) == '-')) {
        sign = (s.charAt(i) == '-') ? -1 : 1;
        i++;
    }

    // build the integer value
    int result = 0;
    while (i < s.length() && Character.isDigit(s.charAt(i))) {
        int digit = Character.getNumericValue(s.charAt(i));
        if (result > Integer.MAX_VALUE / 10 || (result == Integer.MAX_VALUE / 10 && digit > 7)) {
            return (sign == 1) ? Integer.MAX_VALUE : Integer.MIN_VALUE;
        }
        result = result * 10 + digit;
        i++;
    }

    return sign * result;
}

String to Integer (atoi) Ruby Solution

def atoi(s)
  # skip whitespace characters
  i = 0
  while i < s.length && s[i] == ' '
    i += 1
  end

  # handle sign of the number
  sign = 1
  if i < s.length && (s[i] == '+' || s[i] == '-')
    sign = (s[i] == '-') ? -1 : 1
    i += 1
  end

  # build the integer value
  result = 0
  while i < s.length && s[i].match?(/\d/)
    digit = s[i].to_i
    if result > (2**31 - 1) / 10 || (result == (2**31 - 1) / 10 && digit > 7)
      return (sign == 1) ? 2**31 - 1 : -2**31
    end
    result = result * 10 + digit
    i += 1
  end

  sign * result
end

String to Integer (atoi) JavaScript Solution

function atoi(s) {
  // skip whitespace characters
  let i = 0;
  while (i < s.length && s[i] === ' ') {
    i++;
  }

  // handle sign of the number
  let sign = 1;
  if (i < s.length && (s[i] === '+' || s[i] === '-')) {
    sign = (s[i] === '-') ? -1 : 1;
    i++;
  }

  // build the integer value
  let result = 0;
  while (i < s.length && /\d/.test(s[i])) {
    const digit = parseInt(s[i]);
    if (result > (2**31 - 1) / 10 || (result === (2**31 - 1) / 10 && digit > 7)) {
      return (sign === 1) ? 2**31 - 1 : -2**31;
    }
    result = result * 10 + digit;
    i++;
  }

  return sign * result;
}

All three solutions (Java, Ruby, and JavaScript) use an iterative approach to solve the “String to Integer (atoi)” problem. The basic idea behind the iterative approach is to iterate over each character of the string and build the integer value by multiplying the current value by 10 and adding the value of the current character. We also keep track of the sign of the number and handle the cases where the string is empty or does not start with a valid character.

Here are some general steps that are common to all three iterative solutions:

1. Skip whitespace characters: We start by iterating over the string and skipping any whitespace characters (i.e., spaces).
2. Handle sign of the number: We then handle the sign of the number. If the first non-whitespace character is a plus or minus sign, we set the sign accordingly and move to the next character.
3. Build the integer value: We then iterate over the remaining characters of the string and build the integer value. We do this by multiplying the current value by 10 and adding the value of the current character. We also check for overflow and underflow conditions to ensure that the integer value is within the 32-bit signed integer range.
4. Return the integer value: Finally, we return the integer value with the correct sign.