String to Integer (atoi)
Medium · Arrays & Hashing · Explanation and code example
Parse and Clamp
How it works
Read the optional sign, then consume the initial run of digits. Each digit extends the current value by multiplying by ten and adding the digit; stop at the first other character. Clamp as soon as the signed value leaves the 32-bit range.
Steps
- Skip leading spaces and read one optional sign.
- Accumulate consecutive digits.
- Clamp overflow or return the signed value.
Complexity
- Time: O(n) for n input characters.
- Space: Python O(n) for stripped/sliced strings; C++ O(n) for the string copy.
Things to watch for
- A sign without digits returns zero.
- Later digits after a non-digit are ignored;
4193 with wordsyields 4193. - Include both negative and positive overflow cases.
Python code example
class Solution:
def myAtoi(self, s: str) -> int:
s = s.strip()
if not s:
return 0
sign = -1 if s[0] == '-' else 1
if s[0] in {'-', '+'}:
s = s[1:]
num = 0
for c in s:
if not c.isdigit():
break
num = num * 10 + int(c)
if sign * num <= -2**31:
return -2**31
if sign * num >= 2**31 - 1:
return 2**31 - 1
return sign * num
C++ code example
class Solution {
public:
int myAtoi(string s) {
trim(s);
if (s.empty())
return 0;
const int sign = s[0] == '-' ? -1 : 1;
if (s[0] == '+' || s[0] == '-')
s = s.substr(1);
long num = 0;
for (const char c : s) {
if (!isdigit(c))
break;
num = num * 10 + (c - '0');
if (sign * num < INT_MIN)
return INT_MIN;
if (sign * num > INT_MAX)
return INT_MAX;
}
return sign * num;
}
private:
void trim(string& s) {
s.erase(0, s.find_first_not_of(' '));
s.erase(s.find_last_not_of(' ') + 1);
}
};
Source and license
Explanation by LC Tracker. Code adapted from walkccc / Peng-Yu Chen · MIT license. Node types are supplied by LeetCode where needed.