String to Integer (atoi) – LeetCode 8 Solution

by

The LeetCode problem String to Integer (atoi) is a common question that challenges your ability to handle input conversion and edge cases. In this post, we’ll dive into the problem, break down the requirements, and walk through different solutions in Java.

Problem Statement

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 [-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 '.'.

Approach

We’ll explore three solutions with varying levels of complexity and edge case handling:

Solution 1: Using Regular Expressions

A straightforward way to handle this problem is by using regular expressions to parse and filter the valid numeric substring.

Code Implementation

public int myAtoi(String s) {
    s = s.trim(); // Remove leading whitespace
    if (s.isEmpty()) return 0;

    Pattern pattern = Pattern.compile("^[+-]?\\d+");
    Matcher matcher = pattern.matcher(s);

    if (matcher.find()) {
        String numberStr = matcher.group();
        try {
            return Integer.parseInt(numberStr);
        } catch (NumberFormatException e) {
            return numberStr.startsWith("-") ? Integer.MIN_VALUE : Integer.MAX_VALUE;
        }
    }

    return 0;
}

Explanation

  1. Trim leading whitespace: s.trim() removes unnecessary spaces.
  2. Regular expression pattern: ^[+-]?\\d+ matches an optional sign followed by digits.
  3. Conversion: If the number exceeds the 32-bit range, NumberFormatException is caught, and the function returns the appropriate boundary value.

Solution 2: Manual Parsing

Another way to implement this is by manually parsing each character, which provides finer control over edge cases.

Code Implementation

public int myAtoi(String s) {
    int i = 0, n = s.length();
    int result = 0, sign = 1;

    // Ignore leading whitespace
    while (i < n && s.charAt(i) == ' ') i++;

    // Check for optional '+' or '-'
    if (i < n && (s.charAt(i) == '+' || s.charAt(i) == '-')) {
        sign = s.charAt(i) == '-' ? -1 : 1;
        i++;
    }

    // Process digits and build the result
    while (i < n && Character.isDigit(s.charAt(i))) {
        int digit = s.charAt(i) - '0';

        // Overflow and underflow check
        if (result > (Integer.MAX_VALUE - digit) / 10) {
            return sign == 1 ? Integer.MAX_VALUE : Integer.MIN_VALUE;
        }

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

    return result * sign;
}

Explanation

  1. Whitespace skipping: while (i < n && s.charAt(i) == ' ') skips over spaces.
  2. Sign handling: If there’s a ‘+’ or ‘-‘, update the sign accordingly.
  3. Digit extraction: Loop through characters to extract and append digits.
  4. Overflow check: Before adding a new digit, verify if it would exceed Integer.MAX_VALUE. If so, return the boundary value based on the sign.

Solution 3: Enhanced Edge Case Handling with Conditions

In this solution, we build upon the manual parsing approach and add more explicit handling for the problem constraints and common pitfalls.

Code Implementation

public int myAtoi(String s) {
    if (s == null || s.isEmpty()) return 0;

    int i = 0, result = 0, sign = 1, n = s.length();

    // Ignore leading whitespace
    while (i < n && s.charAt(i) == ' ') i++;

    // Determine sign if present
    if (i < n && (s.charAt(i) == '+' || s.charAt(i) == '-')) {
        sign = s.charAt(i++) == '-' ? -1 : 1;
    }

    // Traverse each character
    while (i < n && Character.isDigit(s.charAt(i))) {
        int digit = s.charAt(i++) - '0';

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

        result = result * 10 + digit;
    }

    return result * sign;
}

Explanation

This enhanced solution carefully handles edge cases by checking if s is null or empty. This solution is essentially similar to Solution 2 but includes additional conditions to ensure we don’t run into unexpected errors.

Complexity Analysis for String to Integer

  • Time Complexity: O(N), where N is the length of the input string. We traverse the string once, performing constant-time operations on each character.
  • Space Complexity: O(1), as we only use a few extra variables for processing.

Conclusion

The atoi function requires detailed handling of edge cases, especially around whitespace, signs, and overflow. We explored three different solutions, each progressively more robust. Choose the solution based on your requirements, but be mindful of edge cases to ensure the function behaves as expected.

Let me know if you have questions, or if there’s a specific solution you’d like to understand better!

Related posts:

Master Two Pointer Technique: A Complete Guide
How to solve Two Sum Problem | 2 Solutions
3Sum Leetcode | Leetcode 15 Solution

Leave a comment