8. String to Integer (atoi)

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 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 were read, then the result is 0.
  4. Rounding: If the integer is out of the 32-bit signed integer range [-231, 231 - 1], then round the integer to remain in the range. Specifically, integers less than -231 should be rounded to -231, and integers greater than 231 - 1 should be rounded to 231 - 1.

Return the integer as the final result.

Example 1:

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)
           ^

Example 2:

Input: s = ” -042″

Output: -42

Explanation:

Step 1: "   -042" (leading whitespace is read and ignored)
            ^
Step 2: "   -042" ('-' is read, so the result should be negative)
             ^
Step 3: "   -042" ("042" is read in, leading zeros 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 (0-9), ' ', '+', '-', and '.'.

Problem Description

The myAtoi function is designed to mimic the behavior of the atoi function in C/C++, converting a string to a 32-bit signed integer following a set of specific rules. The steps of the algorithm are:

  1. Start by skipping any leading whitespace in the input string, as these are irrelevant for number conversion.
  2. Identify if the first non-whitespace character is a sign indicator (‘-‘ for negative, ‘+’ for positive). If found, note the sign for the final number. If no sign is specified, the number is considered positive by default.
  3. Read the subsequent characters until a non-digit is encountered or the end of the string is reached. These characters represent the numeric part of the string.
  4. Convert the sequence of digits into an integer. If no digits are found, the result should be 0. Apply the previously noted sign to this integer.
  5. Make sure the resulting integer fits within the range of a 32-bit signed integer. If it does not, “clamp” the value to the nearest boundary of the range, which is either -2**31 or 2**31 - 1.
  6. Return the processed integer as the final result.

A couple of important notes to consider:

  • The only whitespace character to be considered is the space character ' '.
  • All characters after the numeric part of the string should not be ignored, as they can influence the final output if they are non-digits.

Intuition

To convert the string to an integer while following the rules, we need to go step by step:

  1. Skip Whitespaces: Check each character until we encounter a non-whitespace character or the end of the string. This is achieved by using a while loop that increments an index whenever a space is found.
  2. Check for a Sign: Once we hit a non-whitespace character, we decide on the sign of our result. If it’s a ‘-‘ we set the sign to -1, otherwise, we assume it’s positive (1).
  3. Convert String to Integer: We parse the string character by character as long as they are numeric (digits). We need to be mindful of possible overflow past the 32-bit integer range, which happens when our number exceeds the maximum allowed value when multiplied by 10 or when adding the next digit.
  4. Handle Overflows: Since we’re working within the bounds of a signed 32-bit integer, we ensure that any number that goes beyond the limits is clamped to the closest limit, either the lower bound -2**31 or the upper bound 2**31 - 1.

By carefully following each of these steps, we simulate the atoi function’s behavior, producing a 32-bit signed integer from an input string.

Solution Approach

The solution implements the conversion process through a series of steps that correspond to the rules provided in the problem description. Here’s a walk-through of the key components:

  1. Initialization: The function first checks if the string s is not empty. It then initializes important variables such as n for the length of the string, i for the current index, and res for the resulting integer value.
  2. Whitespace Skipping: Using a while loop, the implementation skips over the leading whitespace characters ' ' until a non-whitespace character is encountered by incrementing the i index. If i becomes equal to n (the length of the string), that means the string contained only whitespace, and we return 0.
  3. Sign Detection: The next character is checked to determine the sign of the resultant integer. If it’s a '-', the variable sign is set to -1, otherwise 1. If a sign character is found, i is incremented to move past it.
  4. Integer Conversion: A while loop is used to iterate over the remaining characters of the string, as long as they are digits. Each digit is converted to an integer using int(s[i]) and added to the result res after multiplying the current res by 10 (shifting the number one decimal place to the left). The loop stops if a non-digit character appears.
  5. Overflow Handling: Before adding the new digit to res, we check for potential overflow. For positive numbers, it checks if res is greater than (2**31 - 1) // 10, or if res is equal to (2**31 - 1) // 10 and the next digit (c) is greater than 7 (since 2**31 - 1 ends in 7). For negative numbers, the same logic is applied but with the limits of -2**31. If an overflow is detected, the maximum or minimum 32-bit signed integer value is returned based on the sign.
  6. Result Return: Once the loop finishes, the integer is adjusted with the sign and returned as the result.

The code demonstrates good practices such as:

  • Early exits to avoid unnecessary processing (empty string or string with only spaces).
  • Overflow protection by checking the conditions before the actual overflow could occur.
  • Efficient string traversal by using index arithmetic rather than creating new strings or arrays.

The algorithm does not use any complex data structures, as it only requires integer variables to keep track of the result, the index, and the sign. It is a straightforward and efficient implementation governed by control statements to ensure that the resulting integer adheres to the constraints defined in the problem.

Example Walkthrough

Let’s illustrate the solution approach with a small example. Consider the input string s = " -42" which we want to convert to a 32-bit signed integer following the defined rules.

  1. Initialization:
    • The string s is not empty, so we initialize n=5 (n being the string’s length), i=0 for the current index, and res=0 for the resulting integer value.
  2. Whitespace Skipping:
    • We use a while loop to skip the leading whitespaces. After skipping, i=3 as the first three characters are spaces.
  3. Sign Detection:
    • The next character is '-', which indicates a negative number. We set sign=-1 and increment i to move past the sign, and now i=4.
  4. Integer Conversion:
    • We reach the digits now. With a while loop, we start adding the digits to res. The first character '4' is converted to an integer 4, and res becomes 4. Then i is incremented.
    • Next, i=5 and the character is '2'. We multiply res by 10 (shifting to the left) and add 2, making res=42.
    • i is incremented again, and with i=n, we have reached the end of the string, and the loop ends.
  5. Overflow Handling:
    • During integer conversion, we did not encounter any potential overflow cases, as the number -42 is within the range of a 32-bit signed integer.
  6. Result Return:
    • The final step is to apply the sign to res. With sign=-1, the result becomes -42, which is then returned.

This example adhered to the steps of the algorithm, resulting in the correct 32-bit signed integer conversion of the input string s. The key to solving this problem was carefully handling each character by categorizing it as whitespace, sign, or digit, and applying appropriate operations to avoid overflows.

Solution Implementation

class Solution {
public:
    int myAtoi(string s) 
    {
        int i = 0;  // Index to traverse the string
        int sign = 1;  // Default sign is positive
        long ans = 0;  // Store the result as long to handle overflow cases

        // Skip leading whitespace characters
        while (i < s.length() && s[i] == ' ') 
            i++;

        // Check for optional sign ('+' or '-')
        if (s[i] == '-') {
            sign = -1;  // If negative sign is encountered, set sign to -1
            i++;
        } else if (s[i] == '+') {
            i++;  // If positive sign, just skip it
        }

        // Process the digits in the string
        while (i < s.length()) {
            if (s[i] >= '0' && s[i] <= '9') {  // Check if the character is a digit
                ans = ans * 10 + (s[i] - '0');  // Convert character to digit and add it to the result

                // Check for overflow and underflow
                if (ans > INT_MAX && sign == -1) 
                    return INT_MIN;  // Return INT_MIN if overflow happens with a negative sign
                else if (ans > INT_MAX && sign == 1) 
                    return INT_MAX;  // Return INT_MAX if overflow happens with a positive sign

                i++;  // Move to the next character
            } else {
                return ans * sign;  // If non-digit character is found, return the result
            }
        }

        // Apply the sign and return the final result
        return (ans * sign);
    }
};
Copied!
class Solution {
    public int myAtoi(String s) {
        // Initialize variables: i to track the index, n to track the length, sign to store the sign, and ans to store the result
        int i = 0, n = s.length(), sign = 1, ans = 0;

        // Skip leading whitespace characters
        while (i < n && s.charAt(i) == ' ') {
            i++;
        }

        // Check for optional '+' or '-' sign
        if (i < n && (s.charAt(i) == '+' || s.charAt(i) == '-')) {
            sign = (s.charAt(i) == '-') ? -1 : 1;  // If '-' found, set sign to -1, otherwise set to 1
            i++;  // Move to the next character after the sign
        }
        
        // Process the digits in the string
        while (i < n && s.charAt(i) >= '0' && s.charAt(i) <= '9') {
            int digit = s.charAt(i) - '0';  // Convert the character to its integer value

            // Check for overflow/underflow before updating ans
            if(ans > (Integer.MAX_VALUE - digit) / 10) {
                return (sign == 1) ? Integer.MAX_VALUE : Integer.MIN_VALUE;
            }

            // Update the result
            ans = ans * 10 + digit;
            i++;  // Move to the next character
        }

        // Apply the sign and return the result
        return ans * sign;
    }
}
Copied!
class Solution:
 def myAtoi(self, s: str) -> int:
     # Define the maximum and minimum values for a 32-bit signed integer
     maxR = (2**31) - 1
     minR = -1*(2**31)
     
     sign = 1  # Variable to store the sign of the result (1 for positive, -1 for negative)
     ans = 0  # Variable to store the final result
     
     # Remove leading whitespaces
     s = s.lstrip()
     
     # If the string is empty after removing whitespaces, return 0
     if len(s) == 0:
         return 0
     
     # Check for the sign of the number
     if s[0] == '-':
         sign = -1  # Set the sign to negative
         s = s[1:]  # Remove the sign character from the string
     elif s[0] == '+':
         s = s[1:]  # Remove the plus sign from the string
     
     # Loop through each character in the string
     for i in range(len(s)):
         # If the character is a digit, add it to the result
         if s[i].isdigit():
             ans = ans * 10 + int(s[i])  # Update the result by multiplying by 10 and adding the digit
         else:
             break  # Break the loop if a non-digit character is encountered
     
     # Apply the sign to the result
     ans = ans * sign
     
     # Check for overflow and underflow
     if ans < minR:
         return minR  # Return the minimum value if the result is too small
     elif ans > maxR:
         return maxR  # Return the maximum value if the result is too large
     else:
         return ans  # Return the final result within the valid range
Copied!
int myAtoi(char* s) {
    int count = 0, i = 0, count1 = 0, arr[1000];

    // Skip leading whitespaces
    while(s[i] == ' ') {
        i++;
    }

    // Initialize the sign as positive by default
    int si = 1;

    // Handle signs (+ or -)
    if (s[i] == '-' || s[i] == '+') {
        if (s[i + 1] == '-' || s[i + 1] == '+') { // Check for multiple consecutive signs
            return 0;  // Return 0 if multiple signs are found consecutively
        }
        si = (s[i] == '-') ? -1 : 1;  // Set the sign accordingly
        i++;
    }

    // Variable to store the converted number
    long long int num = 0;  

    // Convert the string of digits into a number
    while(s[i] >= '0' && s[i] <= '9') {
        num = num * 10 + (s[i] - '0');  // Add the current digit to the number

        // Check for overflow or underflow based on the sign
        if (num > INT_MAX && si == 1) {
            return INT_MAX;  // Return INT_MAX if the number overflows
        } else if (num > (long long)INT_MAX + 1 && si == -1) {
            return INT_MIN;  // Return INT_MIN if the number underflows
        }

        i++;  // Move to the next character
    }

    return num * si;  // Return the result with the correct sign
}
Copied!
public class Solution {
    public int MyAtoi(string a)
    {
        // Initialize a StringBuilder to build the result string
        StringBuilder result = new StringBuilder();
        
        // Trim leading and trailing whitespace from the input string
        string s = a.Trim();

        // Loop through each character of the string
        for (int i = 0; i < s.Length; i++)
        {
            // If the character is a letter or '.', return 0 as it's invalid
            if (char.IsLetter(s[i]) || s[i] == '.') return 0;

            // If the character is a digit, process it
            if (char.IsDigit(s[i]))
            {
                // If the second character is a digit, return 0
                if (i > 1) return 0;

                // If it's the first character, process the string based on the index
                if (i == 1) return MyFunc(i - 1, s);

                // Process starting from the first character
                return MyFunc(i, s);
            }
        }
        
        // Return 0 if no valid integer is found
        return 0;
    }

    // This function processes the string from the specified index
    private int MyFunc(int index, string s)
    {
        StringBuilder res = new StringBuilder();

        // If the character is '-', add it to the result and move the index
        if (s[index] == '-'){
            res.Append('-');
            index ++;
        }
        // If the character is '+', move the index
        else if(s[index] == '+') index++;

        // Loop through the rest of the string
        for (int i = index; i < s.Length; i++)
        {
            // If the character is not a digit, check the number and return
            if (!char.IsDigit(s[i]))
            {
                return CheckNumber(res.ToString());
            }
            // Append the digit to the result
            res.Append(s[i]);
        }
        
        // After looping through the string, check the final number and return
        return CheckNumber(res.ToString());
    }

    // This function checks if the parsed number fits within the integer range
    private int CheckNumber(string numberString)
    {
        // Try parsing the string into an integer
        if (int.TryParse(numberString, out int number))
        {
            // If the number exceeds the integer max value, return the max value
            if (number > int.MaxValue)
            {
                return int.MaxValue;
            }
            // If the number is less than the integer min value, return the min value
            else if (number < int.MinValue)
            {
                return int.MinValue;
            }
            // If the number is within the valid range, return it
            else
            {
                return number;
            }
        }
        
        // Return min/max if unable to parse the number
        return (numberString[0] == '-') ? int.MinValue : int.MaxValue;
    }
}
Copied!
/**
* @param {string} s
* @return {number}
*/
var myAtoi = function (s) {
  let result = ""; // Initialize an empty string to store the number
  let readSignal = false; // Flag to check if we've read the sign
  let readNum = false; // Flag to check if we've started reading digits

  // Loop through each character of the string
  for (let i = 0; i < s.length; i++) {
    // Skip leading spaces if we haven't read the signal or number yet
    if (s[i] === " " && !readSignal && !readNum) {
      continue;
    }

    // Check if we encounter the sign '+' or '-'
    if (!readNum && !readSignal) {
      if (s[i] === "+") {
        result += "+"; // Add '+' to result and set readSignal to true
        readSignal = true;
        continue;
      } else if (s[i] === "-") {
        result += "-"; // Add '-' to result and set readSignal to true
        readSignal = true;
        continue;
      }
    }

    // Check if the character is a digit
    if (!isNaN(parseInt(s[i]))) {
      result += s[i]; // Add the digit to the result
      readNum = true; // Set readNum to true since we've started reading digits
    } else {
      break; // Break the loop if a non-digit character is encountered
    }
  }

  let num = parseInt(result); // Convert the result string to a number

  // If the number is NaN (empty string or invalid number), return 0
  if (isNaN(num)) return 0;

  const INT_MAX = 2147483647; // Define the maximum 32-bit integer value
  const INT_MIN = -2147483648; // Define the minimum 32-bit integer value

  // If the number exceeds the 32-bit integer range, return the respective boundary value
  if (num > INT_MAX) return INT_MAX;
  if (num < INT_MIN) return INT_MIN;

  return num; // Return the valid number
};
Copied!
function myAtoi(s: string): number {
    // Define constants for the minimum and maximum 32-bit integer values
    const MIN_VALUE: number = -(2 ** 31);
    const MAX_VALUE: number = 2 ** 31 - 1;
    
    // Convert the string to an integer, return 0 if the conversion is not valid
    const res: number = parseInt(s) || 0;

    // Check if the result is less than the minimum 32-bit integer value
    if (res < MIN_VALUE) return MIN_VALUE;
    
    // Check if the result is greater than the maximum 32-bit integer value
    if (res > MAX_VALUE) return MAX_VALUE;
   
    // Return the valid integer value
    return res;
};
Copied!
class Solution {
    /**
     * @param String $s
     * @return Integer
     */
    function myAtoi($s) {
        // Trim leading and trailing whitespace from the input string
        $s = trim($s);
        
        // Initialize an empty string to accumulate the valid number characters
        $n = '';
        
        // Loop through each character of the string
        for ($i=0; $i<strlen($s); $i++) {
            // Break if the character is neither a number nor a '+' or '-' sign
            if (!is_numeric($s[$i]) && $s[$i] != "+" && $s[$i] != "-") break;
            // Append valid characters to the string $n
            $n .= $s[$i];
        }

        // Convert the accumulated string to an integer
        $n = (int)$n;

        // Handle the case where the number is less than the minimum 32-bit integer
        if ($n < -2147483648) return -2147483648;
        // Handle the case where the number is greater than the maximum 32-bit integer
        if ($n > 2147483647) return 2147483647;

        // Return the final integer value
        return $n;
    }
}
Copied!
class Solution {
    func myAtoi(_ s: String) -> Int {
        // Check if the string contains "+ " (space after '+') and return 0 if it does
        guard !s.contains("+ ") else { return 0 }

        // Convert the string to an integer using NSString's integerValue method
        let val = (s as NSString).integerValue
        
        // Return the integer value but ensure it is within the 32-bit integer range
        return val >= Int32.max ? Int(Int32.max) : max(Int(Int32.min), val)
    }
}
Copied!
class Solution {
    fun myAtoi(s: String): Int {
        var i = 0  // Pointer to traverse the string
        var res = 0  // Variable to store the resulting integer

        // Skip leading whitespaces
        while (i < s.length && s[i] == ' ') i++

        var pos = true  // Variable to determine the sign (positive by default)

        // Check if the current character is a sign ('+' or '-')
        if (i < s.length && (s[i] == '+' || s[i] == '-')) {
            pos = s[i] == '+'  // Set sign and move to the next character
            i++
        }

        // Read the digits and convert them to an integer
        while (i < s.length && s[i] in '0'..'9') {
            var digit = s[i] - '0'  // Convert the current character to a digit
            
            // Check for overflow (if the result is too large to fit in a 32-bit integer)
            if (pos) {
                if (res > (Int.MAX_VALUE - digit) / 10) return Int.MAX_VALUE  // Handle overflow for positive numbers
                res = res * 10 + digit  // Accumulate the result for positive numbers
            } else {
                if (res < (Int.MIN_VALUE + digit) / 10) return Int.MIN_VALUE  // Handle overflow for negative numbers
                res = res * 10 - digit  // Accumulate the result for negative numbers
            }

            i++  // Move to the next character
        }

        // Return the final result
        return res
    }
}
Copied!
class Solution {
  // A map to convert string digits to integer values
  static const digits = {
      "1": 1, "2": 2, "3": 3, "4": 4, "5": 5, "6": 6, "7": 7, "8": 8, "9": 9, "0": 0
  };
  
  // Maximum and Minimum values for a 32-bit signed integer
  static const MAX = 2147483647;
  static const MIN = -2147483648;

  int myAtoi(String s) {
      int res = 0;  // Variable to store the resulting integer
      int sign = 1; // Default sign is positive

      int current = 0; // Pointer to traverse the string

      // Skip leading whitespaces
      while (current < s.length && s[current] == ' ') {
         current++;
      }

      // Check if the current character is a sign ('+' or '-')
      if (current < s.length && (s[current] == '-' || s[current] == '+')) {
          sign = s[current++] == '-' ? -1 : 1;  // Set sign and move to the next character
      }
    
      // Read the digits and convert them to an integer
      while (current < s.length && digits.containsKey(s[current])) {
        int digit = digits[s[current++]]!; // Get the integer value of the current digit
        
        // Check for overflow (if the result is too large to fit in a 32-bit integer)
        if (sign == -1 && res < (MIN + digit) / 10) {
          return MIN;  // Return MIN if overflow occurs
        } else if (res > (MAX - digit) / 10) {
          return MAX;  // Return MAX if overflow occurs
        }

        // Accumulate the result by adding the digit
        res = res * 10 + sign * digit;
      }

      return res;  // Return the final result
  }
}
Copied!
func myAtoi(s string) int {
    // Trim any leading and trailing whitespace from the string
    s = strings.TrimSpace(s)

    // If the string is empty after trimming, return 0
    if len(s) == 0 {
        return 0
    }

    var negative bool
    
    // Check if the first character is a negative sign
    if s[0] == '-' {
        negative = true
        s = s[1:]  // Remove the negative sign for further processing
    } else if s[0] == '+' {
        s = s[1:]  // Remove the positive sign for further processing
    }

    var res int

    // Iterate over the string, processing each character
    for i, c := range s {
        // If the character is not a digit, stop processing
        if c < '0' || c > '9' {
            break
        }

        // Convert the character to a digit and add it to the result
        res = res * 10 + int(s[i]-'0')

        // Check for overflow conditions
        if res > 2147483647 && !negative {
            return 2147483647  // Return INT_MAX if overflow occurs
        }

        if -res < -2147483648 && negative {
            return -2147483648  // Return INT_MIN if underflow occurs
        }
    }

    // If the number was negative, negate the result
    if negative {
        res = -res
    }

    return res  // Return the resulting integer
}
Copied!

Time and Space Complexity

Time Complexity

The time complexity of the given function is O(n), where n is the length of the string. Here’s the breakdown:

  • We iterate once over the string to trim whitespaces, which takes O(n) in the worst case (if all characters are spaces).
  • Checking if the character is a sign ('+' or '-') is O(1).
  • The following while loop iterates over the rest of the string, but it runs at most n times, which is also O(n) in the worst case.
  • Each operation inside the while loop, including checking if a character is a digit, converting it to an integer, checking for overflow, and updating the result, is done in constant time O(1).

Therefore, the dominating factor in the time complexity is the length of the string n, resulting in O(n) overall.

Space Complexity

The space complexity of the function is O(1) because we use a fixed number of integer variables (i, sign, res, flag, and n) and they do not depend on the size of the input string. No additional structures are allocated that would grow with the input size. The space used by s is not counted since it is an input to the function and not additional space allocated by the function itself.

Leave a Reply

Your email address will not be published. Required fields are marked *