Introduction to String to Integer (atoi)
The String to Integer (atoi) problem is a classic algorithmic challenge that frequently appears in coding interviews and competitive programming platforms like LeetCode. The task is to convert a string into a 32-bit signed integer, mimicking the behavior of the C standard library function atoi(). While Python provides built-in methods like int() for string-to-integer conversion, implementing atoi manually teaches fundamental concepts about string parsing, edge-case handling, and numerical boundaries.
This tutorial walks you through the problem statement, a step-by-step solution in Python, edge cases, optimizations, and best practices. By the end, you'll have a robust, interview-ready implementation.
What Is the atoi Problem?
The atoi function converts a string to an integer, but with specific rules that make it more nuanced than a simple int() call. The LeetCode version (Problem #8) defines the following requirements:
- Read in and ignore any leading whitespace.
- Check for an optional sign character (
'+'or'-'). - Read in the next characters until a non-digit character or the end of the string is reached.
- Convert these digits into an integer. If no digits were read, return 0.
- Clamp the result to the 32-bit signed integer range:
[-2^31, 2^31 - 1], which is[-2147483648, 2147483647]. - Return the final integer.
Example Inputs and Outputs
Consider the following examples to understand the expected behavior:
Input: "42"
Output: 42
Input: " -42"
Output: -42
Input: "4193 with words"
Output: 4193
Input: "words and 987"
Output: 0
Input: "-91283472332"
Output: -2147483648 (clamped to minimum)
Why Does atoi Matter?
While you might never need to implement atoi from scratch in production code, the problem is valuable for several reasons:
- String parsing fundamentals: It teaches you how to traverse strings character by character and handle state transitions.
- Edge-case reasoning: The problem is filled with edge cases—empty strings, signs, overflow, leading zeros, and non-digit characters—that test your attention to detail.
- Interview relevance: It's a common interview question because it evaluates both algorithmic thinking and code cleanliness.
- Numerical boundaries: Handling integer overflow is a real concern in systems programming and languages without arbitrary-precision integers.
Step-by-Step Solution in Python
Let's build the solution incrementally. We'll start with a straightforward approach and then refine it.
Step 1: Strip Leading Whitespace
Python strings have a lstrip() method that removes leading whitespace. Alternatively, you can iterate manually with a pointer.
def my_atoi(s: str) -> int:
s = s.lstrip()
if not s:
return 0
# Continue with the rest of the logic
Step 2: Handle the Sign
After stripping whitespace, check if the first character is a sign. Record the sign and advance the pointer.
def my_atoi(s: str) -> int:
s = s.lstrip()
if not s:
return 0
sign = 1
index = 0
if s[0] == '-':
sign = -1
index = 1
elif s[0] == '+':
index = 1
Step 3: Read Digits
Iterate through the string starting from the current index, accumulating digits until a non-digit character is encountered.
def my_atoi(s: str) -> int:
s = s.lstrip()
if not s:
return 0
sign = 1
index = 0
if s[0] == '-':
sign = -1
index = 1
elif s[0] == '+':
index = 1
result = 0
while index < len(s) and s[index].isdigit():
result = result * 10 + int(s[index])
index += 1
Step 4: Apply Sign and Clamp to 32-bit Range
After reading all digits, apply the sign and clamp the result to the 32-bit signed integer range.
def my_atoi(s: str) -> int:
s = s.lstrip()
if not s:
return 0
sign = 1
index = 0
if s[0] == '-':
sign = -1
index = 1
elif s[0] == '+':
index = 1
result = 0
while index < len(s) and s[index].isdigit():
result = result * 10 + int(s[index])
index += 1
result *= sign
INT_MIN = -2 ** 31
INT_MAX = 2 ** 31 - 1
if result < INT_MIN:
return INT_MIN
if result > INT_MAX:
return INT_MAX
return result
Step 5: Test the Solution
Let's verify the implementation against the example inputs:
test_cases = [
("42", 42),
(" -42", -42),
("4193 with words", 4193),
("words and 987", 0),
("-91283472332", -2147483648),
("+0 123", 0),
("", 0),
(" ", 0),
("2147483648", 2147483647),
]
for s, expected in test_cases:
assert my_atoi(s) == expected, f"Failed for '{s}'"
print("All tests passed!")
Optimizing for Early Overflow Detection
The solution above works correctly because Python supports arbitrary-precision integers. However, in languages with fixed-width integers, multiplying and adding could overflow before the final clamp check. To simulate this behavior and make the solution more robust, you can check for overflow during the digit accumulation loop.
Overflow-Aware Implementation
def my_atoi(s: str) -> int:
s = s.lstrip()
if not s:
return 0
sign = 1
index = 0
if s[0] == '-':
sign = -1
index = 1
elif s[0] == '+':
index = 1
INT_MIN = -2 ** 31
INT_MAX = 2 ** 31 - 1
result = 0
while index < len(s) and s[index].isdigit():
digit = int(s[index])
# Check for overflow before adding the digit
if result > INT_MAX // 10 or (result == INT_MAX // 10 and digit > INT_MAX % 10):
return INT_MAX if sign == 1 else INT_MIN
result = result * 10 + digit
index += 1
return sign * result
This version detects overflow during the loop and returns the clamped value immediately, avoiding unnecessary computation and simulating the behavior of fixed-width integer arithmetic.
Alternative Approaches
Using Regular Expressions
For a more concise solution, you can use regular expressions to extract the relevant portion of the string:
import re
def my_atoi_regex(s: str) -> int:
match = re.match(r'^\s*([+-]?\d+)', s)
if not match:
return 0
result = int(match.group(1))
INT_MIN = -2 ** 31
INT_MAX = 2 ** 31 - 1
if result < INT_MIN:
return INT_MIN
if result > INT_MAX:
return INT_MAX
return result
While elegant, the regex approach may be less performant for very long strings and doesn't demonstrate the manual parsing logic that interviewers often want to see.
Using a Deterministic Finite Automaton (DFA)
For a more formal approach, you can model the parsing process as a state machine with states like start, sign, number, and end. This is overkill for this problem but demonstrates a powerful technique applicable to more complex parsing tasks.
def my_atoi_dfa(s: str) -> int:
state = "start"
sign = 1
result = 0
INT_MIN = -2 ** 31
INT_MAX = 2 ** 31 - 1
table = {
"start": ["start", "sign", "number", "end"],
"sign": ["end", "end", "number", "end"],
"number":["end", "end", "number", "end"],
"end": ["end", "end", "end", "end"],
}
def get_col(ch: str) -> int:
if ch.isspace():
return 0
if ch in "+-":
return 1
if ch.isdigit():
return 2
return 3
for ch in s:
col = get_col(ch)
state = table[state][col]
if state == "sign":
if ch == "-":
sign = -1
elif state == "number":
digit = int(ch)
if result > INT_MAX // 10 or (result == INT_MAX // 10 and digit > INT_MAX % 10):
return INT_MAX if sign == 1 else INT_MIN
result = result * 10 + digit
elif state == "end":
break
return sign * result
Best Practices
- Handle edge cases explicitly: Empty strings, strings with only whitespace, and strings with no digits should all return 0.
- Use constants for boundaries: Define
INT_MINandINT_MAXas named constants rather than magic numbers for readability. - Check overflow during accumulation: Even in Python, checking overflow during the loop makes your solution portable to other languages and demonstrates deeper understanding.
- Write comprehensive tests: Include test cases for signs, leading zeros, overflow, underflow, non-digit characters, and mixed content.
- Avoid relying on
int(): The point of the exercise is manual parsing. Usingint()defeats the purpose, though it's fine for comparison testing. - Prefer clarity over cleverness: In interviews, a clear, well-structured solution is better than a clever one-liner that's hard to explain.
Common Pitfalls
- Forgetting to strip whitespace: Leading spaces must be ignored, not treated as invalid characters.
- Mishandling multiple signs: Strings like
"+-12"should return 0, not -12, because only one sign is allowed. - Incorrect overflow clamping: Remember that the negative range is one larger than the positive range in 32-bit signed integers.
- Stopping at the wrong character: Parsing should stop at the first non-digit, not skip ahead to find more digits.
- Ignoring the sign after overflow: When clamping, ensure you return the correct boundary based on the sign.
Conclusion
The String to Integer (atoi) problem is a deceptively simple challenge that tests your ability to parse strings carefully, handle edge cases, and manage numerical boundaries. By following the step-by-step approach outlined in this tutorial—stripping whitespace, handling signs, accumulating digits, and clamping to the 32-bit range—you can build a robust solution that handles all the tricky cases interviewers might throw at you. Whether you choose the manual pointer-based approach, the overflow-aware variant, or even a regex-based solution, the key is to understand the underlying parsing logic and communicate your reasoning clearly. Practice with diverse test cases, and you'll be well-prepared to tackle this problem and similar string-parsing challenges in any coding interview.