Implement myAtoi(s), which turns a string into a 32-bit signed integer the way C's atoi does. Skip leading spaces, then read an optional + or - sign, then read digits until the first non-digit character (ignore the rest). If no digits were read, the result is 0. If the number is outside the range [-2^31, 2^31 - 1], clamp it to the nearest end of that range.
- 0 <= s.length <= 200
- `s` has English letters, digits, spaces, `+`, `-` and `.`
Give it a real try first. Even 15 minutes of struggle makes the solution stick far better.
Intuition
There is no clever algorithm here; the challenge is careful parsing. Use one pointer and move through three stages: skip spaces, read at most one sign, then read digits. The tricky part is overflow: in Java or C++ the running value can overflow before you notice. Checking result > (INT_MAX - d) / 10 before multiplying lets you clamp safely without ever going out of range.
Algorithm
- Set
i = 0; skip spaces whiles[i] == " ". - If
s[i]is+or-, record the sign and move on. - While
s[i]is a digitd: ifresult > (INT_MAX - d) / 10, returnINT_MAXorINT_MINdepending on the sign. - Otherwise set
result = result * 10 + dand move on. - Return
sign * result.
O(n)Space: O(1)"+-12", " +0 123" and "-91283472332" catch most bugs. Clamping to INT_MAX for a positive overflow and to INT_MIN for a negative one works because -INT_MAX - 1 == INT_MIN.class Solution: def myAtoi(self, s: str) -> int: INT_MAX, INT_MIN = 2**31 - 1, -2**31 i, n, sign, result = 0, len(s), 1, 0 while i < n and s[i] == ' ': i += 1 # 1. leading spaces if i < n and s[i] in '+-': # 2. optional sign if s[i] == '-': sign = -1 i += 1 while i < n and s[i].isdigit(): # 3. digits d = ord(s[i]) - ord('0') # result * 10 + d would exceed INT_MAX: clamp now. if result > (INT_MAX - d) // 10: return INT_MAX if sign == 1 else INT_MIN result = result * 10 + d i += 1 return sign * result