8. String to Integer (atoi) 8. String to Integer (atoi) 8. String to Integer (atoi) 8. String to Integer (atoi)
Here’s the question link on LeetCode 8. String to Integer (atoi):
https://leetcode.com/problems/string-to-integer-atoi/description
Contents
Brute Force
We might think of using stoi() to convert the string into an integer.
int ans = stoi(s);
But this doesn’t handle all the requirements:
- We need to ignore leading spaces and stop at the first non-digit.
- We need to handle optional signs.
- The number might overflow, and we need to clamp it instead of throwing an exception.
So let’s implement the conversion ourselves.
Optimal: Traverse the String – O(n)
We can solve this in a single traversal.
There are three main steps:
1. Skip leading spaces and determine the sign.
First, move past all leading spaces. Then check whether the next character is + or -.
while(i < n && s[i] == ' ')
i++;
int sign = 1;
if(i < n && s[i] == '-') {
sign = -1;
i++;
}
else if(i < n && s[i] == '+') {
i++;
}
2. Convert digits into a number.
We keep building our number using:
ans = ans * 10 + digit;
For example, "123":
0 * 10 + 1 = 11 * 10 + 2 = 1212 * 10 + 3 = 123
We continue until we encounter a non-digit.
3. Handle integer overflow.
This is the tricky part.
A 32-bit signed integer can store values between:
\[ -2147483648 \text{ and } 2147483647 \]
Before adding another digit, we need to check whether the next multiplication and addition would cause overflow.
We can use:
if(ans > INT_MAX / 10 ||
(ans == INT_MAX / 10 && digit > 7))
Why 7?
Because INT_MAX is 2147483647, and its last digit is 7.
For a negative number, the absolute value can reach 2147483648, so we use 8 as the last digit limit.
If overflow happens, directly return INT_MAX or INT_MIN depending on the sign.
class Solution {
public:
int myAtoi(string s) {
int n = s.size();
int i = 0;
// Skip leading spaces
while(i < n && s[i] == ' ')
i++;
// Determine sign
int sign = 1;
if(i < n && s[i] == '-') {
sign = -1;
i++;
}
else if(i < n && s[i] == '+') {
i++;
}
long long ans = 0;
// Convert digits
while(i < n && s[i] >= '0' && s[i] <= '9') {
long long digit = s[i] - '0';
// Check overflow before multiplying
if(ans > INT_MAX / 10 ||
(ans == INT_MAX / 10 && digit > (sign == 1 ? 7 : 8))) {
return sign == 1 ? INT_MAX : INT_MIN;
}
ans = ans * (long long) 10 * 1LL + digit;
i++;
}
return ans * sign;
}
};