String to Integer ATOI

Problem Link

8. String to Integer (atoi) – LeetCode

Problem Statement

Implement the function myAtoi(string s) which converts a string to a 32-bit signed integer (similar to C/C++'s atoi function).

Rules:

1. Ignore leading whitespaces.

2. Check for optional sign (+ or -).

3. Convert the following digits to an integer until a non-digit character is found.

4. If no digits were found → return 0.

5. Clamp the value in range [-2³¹, 2³¹ - 1].

Examples

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 = "words and 987"
Output: 0

Example 5:

Input: s = "-91283472332"
Output: -2147483648  // Clamped to Integer.MIN_VALUE

Constraints

• 0 <= s.length <= 200

• s may contain: letters (a-z, A-Z), digits (0-9), spaces, +, -, .

Intuition

We need to parse the string manually by processing it character by character:

1. Skip whitespace

2. Identify sign

3. Read digits while tracking overflow

4. Stop at first non-digit after digits begin

5. Return the integer result with sign and clamping if needed

Approach

• Trim whitespace using String.trim()

• Read the optional sign

• Recursively (or iteratively) convert digits into an integer

• Detect overflow by checking if num > (Integer.MAX_VALUE - digit) / 10

• Return final result with sign

Code (Java - Recursive Version)

class Solution {
    public int myAtoi(String s) {
        s = s.trim(); // Step 1: Trim leading whitespace
        if (s.length() == 0) return 0;

        boolean isNeg = false;
        int idx = 0;

        // Step 2: Handle optional sign
        if (s.charAt(0) == '-' || s.charAt(0) == '+') {
            isNeg = s.charAt(0) == '-';
            idx++;
        }

        // Step 3: Convert digits recursively
        return helper(s, idx, 0, isNeg);
    }

    private int helper(String s, int idx, int num, boolean isNeg) {
        if (idx >= s.length() || !Character.isDigit(s.charAt(idx))) {
            return isNeg ? -num : num;
        }

        int digit = s.charAt(idx) - '0';

        // Step 4: Check for overflow
        if (num > (Integer.MAX_VALUE - digit) / 10) {
            return isNeg ? Integer.MIN_VALUE : Integer.MAX_VALUE;
        }

        return helper(s, idx + 1, num * 10 + digit, isNeg);
    }
}

Time & Space Complexity

Dry Run

Input:

s = "   -042"

Steps:

• Trimmed string: "-042"

• isNeg = true

• Read digits: 0 → 4 → 2

• Final value = 42, with isNeg = true

• Output: -42

Alternate Iterative Version

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

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

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

    // 3. Convert digits and detect overflow
    while (i < n && Character.isDigit(s.charAt(i))) {
        int digit = s.charAt(i++) - '0';

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

        result = result * 10 + digit;
    }

    return result * sign;
}

Conclusion

This problem tests your string parsing skills, attention to edge cases (signs, overflow, whitespace), and knowledge of bounds checking in numerical computation.