LeetCode Problem

Problem Description

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

Examples

Input: s = "42"
Output: 42

Input: s = " -42"
Output: -42

Input: s = "4193 with words"
Output: 4193

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

Input: s = "-91283472332"
Output: -2147483648

Constraints

0 <= s.length <= 200
s consists of English letters (lower-case and upper-case), digits (0-9), ' ', '+', '-', and '.'.

Follow-up

Approach to Solve

Iterate through the string, handling whitespace, sign, and digit characters while checking for overflow conditions.

Code Implementation

class Solution:
    def myAtoi(self, s: str) -> int:
        s = s.strip()
        if not s:
            return 0
        sign = 1
        if s[0] == '-' or s[0] == '+':
            sign = -1 if s[0] == '-' else 1
            s = s[1:]
        result = 0
        for char in s:
            if not char.isdigit():
                break
            result = result * 10 + int(char)
            if result > 2**31 - 1:
                return 2**31 - 1 if sign == 1 else -2**31
        return sign * result

class Solution {
    public int myAtoi(String s) {
        s = s.trim();
        if (s.isEmpty()) return 0;
        int sign = 1, i = 0;
        if (s.charAt(0) == '-' || s.charAt(0) == '+') {
            sign = s.charAt(0) == '-' ? -1 : 1;
            i++;
        }
        long result = 0;
        while (i < s.length() && Character.isDigit(s.charAt(i))) {
            result = result * 10 + (s.charAt(i) - '0');
            if (result > Integer.MAX_VALUE) {
                return sign == 1 ? Integer.MAX_VALUE : Integer.MIN_VALUE;
            }
            i++;
        }
        return (int)result * sign;
    }
}

class Solution {
public:
    int myAtoi(string s) {
        s = s.erase(0, s.find_first_not_of(' '));
        if (s.empty()) return 0;
        int sign = 1, i = 0;
        if (s[0] == '-' || s[0] == '+') {
            sign = s[0] == '-' ? -1 : 1;
            i++;
        }
        long long result = 0;
        while (i < s.length() && isdigit(s[i])) {
            result = result * 10 + (s[i] - '0');
            if (result > INT_MAX) {
                return sign == 1 ? INT_MAX : INT_MIN;
            }
            i++;
        }
        return sign * result;
    }
};

Explanation

The String to Integer (atoi) problem is solved using a careful step-by-step approach:

Trim leading and trailing whitespace from the input string.
Check if the resulting string is empty. If so, return 0.
Determine the sign of the number:
- If the first character is '+' or '-', set the sign accordingly and move to the next character.
- Otherwise, assume the sign is positive.
Iterate through the remaining characters:
- If the character is a digit, add it to the result: result = result * 10 + digit_value.
- If the character is not a digit, stop the iteration.
Check for overflow at each step:
- If result > INT_MAX, return INT_MAX for positive numbers or INT_MIN for negative numbers.
Apply the sign to the final result and return it.

This approach handles various edge cases and constraints:

It correctly processes leading whitespace and optional sign characters.
It stops processing at the first non-digit character after the number.
It handles overflow by checking against INT_MAX at each step.
It works for both positive and negative numbers.

The time complexity is O(n) where n is the length of the string, as we potentially need to scan the entire string once. The space complexity is O(1) as we only use a constant amount of extra space regardless of the input size.

Complexity

Time Complexity: O(n)
Space Complexity: O(1)