#8

Medium

auto_awesomeString-driven solution strategy

LeetCode Problem Workspace

String to Integer (atoi)

Convert a string to a 32-bit signed integer by carefully parsing characters, handling signs, and ignoring invalid trailing input.

string

Problem Statement

Implement the function myAtoi(string s) that converts a string into a 32-bit signed integer. The parsing should skip any leading spaces, interpret an optional '+' or '-' sign, and read consecutive digits until a non-digit character or the end of the string is reached. The final integer must be clamped within the 32-bit signed integer range if it exceeds limits.

The function should ignore any characters following the initial valid numeric sequence. Input strings may include letters, digits, whitespace, and symbols, but only the contiguous numeric portion with an optional sign counts toward the integer result. Return 0 if no valid conversion can be performed.

Examples

Example 1

Input: See original problem statement.

Output: See original problem statement.

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: See original problem statement.

Output: See original problem statement.

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: See original problem statement.

Output: See original problem statement.

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) ^

Constraints

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

Solution Approach

Stepwise Parsing Strategy

Begin by removing leading whitespace, then check for a '+' or '-' to determine the sign. Iterate through the string, accumulating digits into a result integer, and stop at the first non-digit character. This ensures precise extraction from a string-driven input.

Overflow Handling

While accumulating digits, check if adding the next digit would exceed the 32-bit signed integer range. If overflow is detected, clamp the result to INT_MAX or INT_MIN depending on the sign. This prevents common failure modes in atoi conversions.

Edge Case Considerations

Handle empty strings, strings with only whitespace, and strings with no digits after optional signs by returning 0. This addresses typical pitfalls like invalid input or early termination scenarios.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(n) where n is the length of the string, because each character is processed at most once. Space complexity is O(1) as only a few integer variables are maintained, regardless of input length.

What Interviewers Usually Probe

Clarifies how whitespace and signs are handled before digit accumulation.
Asks about integer overflow behavior when parsing large numeric strings.
Checks handling of non-digit characters following the numeric portion.

Common Pitfalls or Variants

Common pitfalls

Failing to skip leading spaces before detecting the sign.
Ignoring overflow cases, which can produce incorrect or runtime errors.
Incorrectly processing strings with no valid digits, leading to non-zero returns.

Follow-up variants

Converting strings with different numeric bases such as hexadecimal or binary.
Handling floating-point numbers by extending parsing to decimals.
Parsing strings with embedded commas or formatting characters into integers.

FAQ

What should myAtoi return if the string is empty or has no digits?

Return 0 when no valid numeric characters are found after optional whitespace and sign handling.

How does the function handle integer overflow?

Clamp results to INT_MAX (2^31-1) or INT_MIN (-2^31) if the numeric conversion exceeds 32-bit signed limits.

Can myAtoi handle strings with letters or symbols after digits?

Yes, parsing stops at the first non-digit character and only the valid numeric prefix contributes to the result.

Does the optional '+' or '-' sign affect parsing if there is leading whitespace?

Yes, leading whitespace is skipped first, then the sign is detected to determine the integer's positivity or negativity.

How does this solution reflect the string-driven solution strategy?

It processes the string sequentially, carefully handling each character and sign, emphasizing edge case management and parsing precision.

terminal

Solution

Solution 1: Traverse the String

First, we determine whether the string is empty. If it is, we directly return $0$.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

class Solution:
    def myAtoi(self, s: str) -> int:
        if not s:
            return 0
        n = len(s)
        if n == 0:
            return 0
        i = 0
        while s[i] == ' ':
            i += 1
            if i == n:
                return 0
        sign = -1 if s[i] == '-' else 1
        if s[i] in ['-', '+']:
            i += 1
        res, flag = 0, (2**31 - 1) // 10
        while i < n:
            if not s[i].isdigit():
                break
            c = int(s[i])
            if res > flag or (res == flag and c > 7):
                return 2**31 - 1 if sign > 0 else -(2**31)
            res = res * 10 + c
            i += 1
        return sign * res

Continue Practicing

#6 zigzag conversion #10 regular expression matching #5 longest palindromic substring