LeetCode 8 - String to Integer (atoi)

Question:

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

The algorithm for myAtoi(string s) is as follows:

Read in and ignore any leading whitespace.
Check if the next character (if not already at the end of the string) is '-' or '+'. Read this character in if it is either. This determines if the final result is negative or positive respectively. Assume the result is positive if neither is present.
Read in next the characters until the next non-digit character or the end of the input is reached. The rest of the string is ignored.
Convert these digits into an integer (i.e. "123" -> 123, "0032" -> 32). If no digits were read, then the integer is 0. Change the sign as necessary (from step 2).
If the integer is out of the 32-bit signed integer range [-2³¹, 2³¹ - 1], then clamp the integer so that it remains in the range. Specifically, integers less than -2³¹ should be clamped to -2³¹, and integers greater than 2³¹ - 1 should be clamped to 2³¹ - 1.
Return the integer as the final result.

Note:

Only the space character ' ' is considered a whitespace character.
Do not ignore any characters other than the leading whitespace or the rest of the string after the digits.

Example 1:

Input: s = "42"

Output: 42

Explanation: The underlined characters are what is read in, 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)

The parsed integer is 42.

Since 42 is in the range [-2³¹, 2³¹ - 1], the final result is 42.

Example 2:

Input: s = " -42"

Output: -42

Explanation:

Step 1: " -42" (leading whitespace is read and ignored)

Step 2: " -42" ('-' is read, so the result should be negative)

Step 3: " -42" ("42" is read in)

The parsed integer is -42.

Since -42 is in the range [-2³¹, 2³¹ - 1], the final result is -42.

Example 3:

Input: s = "4193 with words"

Output: 4193

Explanation:

Step 1: "4193 with words" (no characters read because there is no leading whitespace)

Step 2: "4193 with words" (no characters read because there is neither a '-' nor '+')

Step 3: "4193 with words" ("4193" is read in; reading stops because the next character is a non-digit)

The parsed integer is 4193.

Since 4193 is in the range [-2³¹, 2³¹ - 1], the final result is 4193.

Answer:

The C++ function myAtoi converts a string to an integer by ignoring leading whitespaces, considering an optional sign, accumulating digits until a non-digit is encountered, and handling overflows by clamping the result to the limits of a 32-bit signed integer.

Approach :

1. Initialization: The function begins by initializing several variables:

n: The size of the string.
res: A double used to accumulate the result. This choice allows handling potential overflow situations more gracefully, as it has a wider range than an int.
Flags dig (digit found), posi (positive sign found), neg (negative sign found), and other (any other character found) to track the state of parsing.

2. Whitespace Skipping: The function starts with a while loop to skip any leading whitespace characters in the input string.

3. Parsing: The function then enters a for loop to parse the rest of the string:

If a digit is encountered ('0' through '9'), it multiplies the current res by 10 (shifting it one decimal place to the left) and adds the numerical value of the current digit.
If a non-digit character is encountered before any digit, the function checks for '+' and '-'. It sets the respective flag if found and only if no other sign has been processed. Any other character leads to setting the other flag, indicating an invalid input, and breaking the loop.
If digits have been encountered (dig is true) and the function then encounters a non-digit character, it breaks out of the loop as it has reached the end of the numeric part of the string.

4. Post-Parsing Checks: After the loop, the function checks for invalid states:

If both posi and neg flags are true, it means the input is invalid (both signs were found), so it returns 0.
If the neg flag is true, it negates res to make the number negative.

5. Overflow Handling: Before returning, the function checks if res exceeds the range of a 32-bit signed integer (INT_MAX and INT_MIN) and clamps the value accordingly.

6. Return: Finally, it casts res to an int and returns it.

Time Complexity:

The function iterates over each character of the string exactly once. Therefore, the time complexity is O(n), where n is the length of the input string.

Space Complexity:

The space complexity is O(1). Regardless of the input size, the function uses a constant amount of space for its variables (n, res, the flags, and a few others for control flow).

Code:

class Solution:
    def myAtoi(self, s: str) -> int:
        n = len(s)
        res = 0
        dig = False
        posi = False
        neg = False
        other = False
        
        i = 0
        while i < n and s[i] == ' ':
            i += 1
            
        for j in range(i, n):
            if other:
                break
                
            if '0' <= s[j] <= '9':
                res = (res * 10) + (ord(s[j]) - ord('0'))
                dig = True
            else:
                if dig:
                    break
                
                elif s[j] == '-' and not neg:
                    neg = True
                    
                elif s[j] == '+' and not posi:
                    posi = True
                    
                else:
                    other = True
                    
        if posi and neg:
            return 0
        
        if neg:
            res = -res
            
        if res > 2**31 - 1:
            return 2**31 - 1
        
        if res < -2**31:
            return -2**31
        
        return int(res)