Watch 10 video solutions for String to Integer (atoi), a medium level problem involving String. This walkthrough by Ayushi Sharma has 78,956 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
Implement the myAtoi(string s) function, which converts a string to a 32-bit signed integer.
The algorithm for myAtoi(string s) is as follows:
" ").'-' or '+', assuming positivity if neither present.[-231, 231 - 1], then round the integer to remain in the range. Specifically, integers less than -231 should be rounded to -231, and integers greater than 231 - 1 should be rounded to 231 - 1.Return the integer as the final result.
Example 1:
Input: s = "42"
Output: 42
Explanation:
The underlined characters are what is read in and the caret is the current reader position.
Step 1: "42" (no characters read because there is no leading whitespace)
^
Step 2: "42" (no characters read because there is neither a '-' nor '+')
^
Step 3: "42" ("42" is read in)
^
Example 2:
Input: s = " -042"
Output: -42
Explanation:
Step 1: " -042" (leading whitespace is read and ignored)
^
Step 2: " -042" ('-' is read, so the result should be negative)
^
Step 3: " -042" ("042" is read in, leading zeros ignored in the result)
^
Example 3:
Input: s = "1337c0d3"
Output: 1337
Explanation:
Step 1: "1337c0d3" (no characters read because there is no leading whitespace)
^
Step 2: "1337c0d3" (no characters read because there is neither a '-' nor '+')
^
Step 3: "1337c0d3" ("1337" is read in; reading stops because the next character is a non-digit)
^
Example 4:
Input: s = "0-1"
Output: 0
Explanation:
Step 1: "0-1" (no characters read because there is no leading whitespace)
^
Step 2: "0-1" (no characters read because there is neither a '-' nor '+')
^
Step 3: "0-1" ("0" is read in; reading stops because the next character is a non-digit)
^
Example 5:
Input: s = "words and 987"
Output: 0
Explanation:
Reading stops at the first non-digit character 'w'.
Constraints:
0 <= s.length <= 200s consists of English letters (lower-case and upper-case), digits (0-9), ' ', '+', '-', and '.'.Problem Overview: Convert a string into a 32-bit signed integer following rules similar to the C/C++ atoi function. You must ignore leading whitespace, detect an optional + or - sign, read digits until a non-digit appears, and clamp the result within the 32-bit signed integer range [-2^31, 2^31-1].
Approach 1: Iterative Parsing and Conversion (O(n) time, O(1) space)
Scan the string from left to right while maintaining a running integer result. First skip leading whitespace using a pointer. Then check for an optional sign and store whether the number is negative. Continue iterating while characters are digits, updating the result with result = result * 10 + digit. During each step, check for overflow by comparing against INT_MAX / 10 before multiplying; if overflow would occur, clamp to INT_MAX or INT_MIN. This approach directly simulates how numeric parsing works in low-level libraries and runs in O(n) time with O(1) space.
This technique relies on careful character inspection and arithmetic overflow checks. It’s essentially a controlled state machine over the string. Problems like this often appear under string processing and manual parsing tasks where built-in conversion functions are restricted.
Approach 2: Regular Expression Approach (O(n) time, O(n) space)
Use a regular expression to extract the valid numeric prefix from the string. A pattern such as ^\s*[+-]?\d+ captures leading whitespace, an optional sign, and a sequence of digits. After extracting the match, convert it to an integer using the language’s numeric conversion function. Finally clamp the value within the 32-bit signed range. Regex simplifies the parsing logic by delegating pattern matching to the regex engine.
This approach is concise and expressive, especially in languages like Python or JavaScript with strong regex support. However, it uses extra memory for the match object and hides some parsing logic inside the regex engine. It’s still linear O(n) time because the pattern scans the string once.
Regex-based solutions appear in some production code when input validation or token extraction is required. These patterns frequently show up in string manipulation and lightweight parsing workflows.
Recommended for interviews: Iterative parsing and conversion. Interviewers want to see how you handle character iteration, numeric accumulation, and overflow detection manually. The regex approach demonstrates knowledge of pattern matching, but the iterative method shows stronger control over algorithm design and edge cases.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Iterative Parsing and Conversion | O(n) | O(1) | Preferred for interviews and low-level parsing where overflow checks and manual control are required |
| Regular Expression Approach | O(n) | O(n) | Useful for quick input parsing or when regex is already used for validation |