String To Integer Atoi Solution for Microsoft

Company: Microsoft · Difficulty: Hard · Topics: String, Math

Problem Statement

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:

1. Read in and ignore any leading whitespace.

2. 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. If neither is present, then the result is positive.

3. 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.

4. 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).

5. If the integer is out of the 32-bit signed integer range [-2^31, 2^31 - 1], then clamp the integer so that it remains in the range. Specifically, integers less than -2^31 should be clamped to -2^31, and integers greater than 2^31 - 1 should be clamped to 2^31 - 1.

Examples

Example 1:

Input: s = "42"

Output: 42

Explanation: Leading whitespace is ignored, and no sign is present.

Example 2:

Input: s = " -42"

Output: -42

Explanation: Leading whitespace is ignored, '-' is read, then digits are read.

Example 3:

Input: s = "4193 with words"

Output: 4193

Explanation: Digits are read until a non-digit character is encountered.

Example 4:

Input: s = "words and 987"

Output: 0

Explanation: No digits are read, so result is 0.

Example 5:

Input: s = "-91283472332"

Output: -2147483648

Explanation: Result is clamped to INT_MIN.

Intuition

The key insight is to process the string character by character, following the specific rules for atoi conversion. We need to handle whitespace, signs, digits, and overflow conditions carefully.

Approach

Approach 1: State Machine (Optimal)

1. Define states: WHITESPACE, SIGN, DIGIT, END

2. Process each character based on current state

3. Handle overflow by checking before multiplication

4. Return result with proper sign

Approach 2: Simple Parsing

1. Skip leading whitespace

2. Handle sign character

3. Read digits and build number

4. Check for overflow at each step

Approach 3: Regular Expression

1. Use regex to extract valid number pattern

2. Parse the extracted string

3. Handle edge cases separately

Dry Run

Let's trace through Example 2: s = " -42"

State Machine Approach:

State: WHITESPACE, char=' ': continue
State: WHITESPACE, char=' ': continue
State: WHITESPACE, char='-': set sign=-1, state=SIGN
State: SIGN, char='4': result=4, state=DIGIT
State: DIGIT, char='2': result=42, state=DIGIT
State: DIGIT, char=' ': stop, return -42

Solution

Note: This solution provides multiple approaches to solve the problem. Choose the one that best fits your understanding and requirements.

Key Insights:

1. State Machine: Clear separation of parsing phases

2. Overflow Handling: Check before multiplication to avoid overflow

3. Edge Cases: Handle empty strings, signs, and non-digits properly

Edge Cases:

Empty string: return 0
Only whitespace: return 0
No digits after sign: return 0
Overflow: clamp to INT_MIN/INT_MAX
Multiple signs: ignore after first

Time Complexity

All Approaches: O(n) where n is string length

Space Complexity

All Approaches: O(1) extra space