String to Integer (atoi)

Description

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 is 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]$, 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

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

Example 3:
Input: s = "1337c0d3"
Output: 1337

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

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

Constraints:

• $0\le \text{s.length}\le 200$
• s consists of English letters, digits (0-9), ' ', '+', '-', and '.'.

---

Approach 1: Iterative Direct Simulation ($O(N)$ Time, $O(1)$ Space)

Intuition

Follow the rules step-by-step:

1. Advance pointer i past all leading spaces.
2. Check for an optional + or - sign.
3. Process incoming digit characters sequentially.
4. Prevent 32-bit integer overflow before appending each digit by checking against Integer.MAX_VALUE / 10.

class Solution {
    public int myAtoi(String s) {
        int i = 0;
        int n = s.length();
        int sign = 1;
        int result = 0;
 
        // Step 1: Skip leading whitespace
        while (i < n && s.charAt(i) == ' ') {
            i++;
        }
 
        // Step 2: Handle sign declaration
        if (i < n && (s.charAt(i) == '+' || s.charAt(i) == '-')) {
            sign = (s.charAt(i) == '-') ? -1 : 1;
            i++;
        }
 
        // Step 3: Convert digits and check 32-bit overflow
        while (i < n && Character.isDigit(s.charAt(i))) {
            int digit = s.charAt(i) - '0';
 
            // Check for potential overflow before updating result
            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 result * sign;
    }
}
 

Complexity

• Time Complexity: $O(N)$ — Single pass over the string of length $N$.
• Space Complexity: $O(1)$ — Uses a few primitive variables.

---

Approach 2: Deterministic Finite Automaton / State Machine ($O(N)$ Time, $O(1)$ Space)

Intuition

Model the parsing process as a State Machine with 4 distinct states:

• State 0 (Start): Reading whitespace.
• State 1 (Sign): Sign processed.
• State 2 (In Number): Reading digits and building integer.
• State 3 (End): Stopped upon encountering a non-digit character or overflow.

This guarantees robust handling of all edge cases without deeply nested condition checks.

class Solution {
    static class StateMachine {
        private int currentState = 0; // 0: Start, 1: Sign, 2: In Number, 3: End
        private int sign = 1;
        private int result = 0;
 
        public void transition(char ch) {
            if (currentState == 3) return;
 
            if (currentState == 0) {
                if (ch == ' ') return;
                if (ch == '+' || ch == '-') {
                    sign = (ch == '-') ? -1 : 1;
                    currentState = 1;
                    return;
                }
                if (Character.isDigit(ch)) {
                    currentState = 2;
                    appendDigit(ch - '0');
                    return;
                }
                currentState = 3; // Invalid leading char
            } else if (currentState == 1 || currentState == 2) {
                if (Character.isDigit(ch)) {
                    currentState = 2;
                    appendDigit(ch - '0');
                } else {
                    currentState = 3; // Stop on non-digit
                }
            }
        }
 
        private void appendDigit(int digit) {
            if (result > Integer.MAX_VALUE / 10 || 
               (result == Integer.MAX_VALUE / 10 && digit > 7)) {
                result = (sign == 1) ? Integer.MAX_VALUE : Integer.MIN_VALUE;
                currentState = 3;
            } else {
                result = result * 10 + digit;
            }
        }
 
        public int getResult() {
            if (result == Integer.MAX_VALUE || result == Integer.MIN_VALUE) {
                return result;
            }
            return result * sign;
        }
    }
 
    public int myAtoi(String s) {
        StateMachine sm = new StateMachine();
        for (int i = 0; i < s.length(); i++) {
            sm.transition(s.charAt(i));
        }
        return sm.getResult();
    }
}
 

Complexity

• Time Complexity: $O(N)$ — Processes each character once through state transitions.
• Space Complexity: $O(1)$ — Constant space for state variables.

---

Easy Memory Rule

“Skip spaces $\to$ grab optional sign $\to$ process digits while checking result > MAX / 10 before multiplying.”