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.
In this approach, we manually parse the string character by character. First, we skip any leading whitespace. Then, we determine the sign of the number by checking the next character. After we've set up the sign, we convert succeeding string characters to a number as long as they are digits, and check if the number overflows the 32-bit signed integer range. The iterative parsing continues until we encounter a non-numeric character.
The function begins by traversing any leading whitespace in the input string. If the next character is a '-' or '+', it sets the sign accordingly and moves to the next character. We update a 'result' variable as we iterate over each digit, checking against overflow conditions. This result is carefully treated as a long to avoid overflow, then cast to an int at the end. Edge cases, including overflow beyond 32-bit bounds, are also managed explicitly.
Time Complexity: O(n), where n is the length of the string because we traverse the string once.
Space Complexity: O(1), since we only use a fixed amount of extra space.
Using regular expressions simplifies extracting the integer portion from a string. This involves defining a regular expression to match the pattern for potential number initializations, determining whether followed by valid digits until non-numeric encounters or string end, and then mathematically transforming results. While elegant, care still needs to be taken on handling sign and range boundaries.
This JavaScript function utilizes a regular expression to detect any leading spaces, an optional sign, and a sequence of digits at the start of the string. The parseInt utility parses the integer, which is tempered by limits for overflowing numbers using conditional returns.
JavaScript
Python
Time Complexity: O(n), regular expression parsing inspects the input sequence linearly.
Space Complexity: O(1), denoting the small constant space taken up by the quantitative calculation.
First, we determine whether the string is empty. If it is, we directly return 0.
Otherwise, we need to traverse the string, skip the leading spaces, and determine whether the first non-space character is a positive or negative sign.
Then we traverse the following characters. If it is a digit, we judge whether adding this digit will cause integer overflow. If it does, we return the result according to the positive or negative sign. Otherwise, we add the digit to the result. We continue to traverse the following characters until we encounter a non-digit character or the traversal ends.
After the traversal ends, we return the result according to the positive or negative sign.
The time complexity is O(n), where n is the length of the string. We only need to process all characters in turn. The space complexity is O(1).
| Approach | Complexity |
|---|---|
| Iterative Parsing and Conversion | Time Complexity: O(n), where n is the length of the string because we traverse the string once. Space Complexity: O(1), since we only use a fixed amount of extra space. |
| Regular Expression Approach | Time Complexity: O(n), regular expression parsing inspects the input sequence linearly. Space Complexity: O(1), denoting the small constant space taken up by the quantitative calculation. |
| Traverse the String | — |
| 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 |
String to Integer atoi 🔥| Leetcode 8 | String • Ayushi Sharma • 78,956 views views
Watch 9 more video solutions →Practice String to Integer (atoi) with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor