grid47 Exploring patterns and algorithms
Nov 6, 2024
6 min read
Solution to LeetCode 8: String to Integer (atoi) Problem
Convert a string to a 32-bit signed integer, handling whitespaces, optional signs, and non-digit characters.
Problem
Approach
Steps
Complexity
Input: The input is a string s containing English letters, digits, spaces, and optional signs.
Example: s = ' 42'
Constraints:
• 0 <= s.length <= 200
• s consists of English letters (lowercase and uppercase), digits (0-9), spaces, '+' or '-', and possibly other non-digit characters.
Output: Return the integer value represented by the string after ignoring leading spaces and processing digits, within the 32-bit signed integer range.
Example: For input s = '42', the output is 42.
Constraints:
• The result must be within the range of a 32-bit signed integer: [-231, 231 - 1].
Goal: Parse the string, handle optional signs, ignore non-digit characters after the first integer, and ensure the result remains within the 32-bit signed integer limits.
Steps:
• Skip leading spaces.
• Check for a '+' or '-' sign to determine the number's sign.
• Parse the digits until a non-digit character is encountered.
• If no digits are found, return 0.
• Clamp the result to fit within the 32-bit signed integer range.
Goal: Handle edge cases such as empty strings, leading spaces, and large numbers.
Steps:
• The string may have leading or trailing spaces.
• The string may contain a sign before the number.
• The number may exceed the 32-bit signed integer range.
Assumptions:
• The input string can contain digits, spaces, signs, and other characters.
• If no valid number is found, the result should be 0.
• Input: Example 1: s = ' 42'
• Explanation: The function processes the string '42', ignoring leading spaces, and returns the integer 42.
• Input: Example 2: s = ' - 0345'
• Explanation: The function reads the number '-345' after ignoring the spaces and the leading zeros.
• Input: Example 3: s = '56x89'
• Explanation: The function reads '56' and stops at the character 'x', returning 56.
• Input: Example 4: s = '0000000000'
• Explanation: All zeros are ignored, resulting in 0.
• Input: Example 5: s = 'words 123'
• Explanation: Since the string starts with non-numeric characters, the function returns 0.
Approach: The approach is to iterate through the string, parsing the number while handling edge cases and ensuring the final result is within the bounds of a 32-bit signed integer.
Observations:
• We need to handle whitespace, signs, and non-digit characters properly.
• The result must be clamped to fit within a 32-bit signed integer range.
• The algorithm should stop reading when a non-digit character is encountered after parsing valid digits.
Steps:
• Trim leading spaces.
• Identify the sign of the number.
• Process digits until a non-digit character is found.
• Clamp the result to the 32-bit integer range.
Empty Inputs:
• An empty string should return 0.
Large Inputs:
• Large inputs may exceed the 32-bit integer range and should be clamped accordingly.
Special Values:
• If the string contains no digits, return 0.
Constraints:
• Handle strings with spaces, signs, and non-digit characters.
intmyAtoi(string s) {
int res =0;
int sgn =1;
int i =0;
while(i < s.size() && s[i] ==' ') i++;
if(i < s.size() && (s[i] =='+'|| s[i] =='-'))
sgn = (s[i++] =='+')?1:-1;
while(i < s.size() && s[i] >='0'&& s[i] <='9') {
if(res > INT_MAX/10|| (res == INT_MAX/10&& ((s[i]-'0')>(INT_MAX %10))))
return (sgn >0)?INT_MAX: INT_MIN;
res = res *10+ (s[i++] -'0');
// cout << res << " ";
}
return sgn * res;
}
1 : Function Declaration
intmyAtoi(string s) {
Declare the `myAtoi` function, which takes a string `s` as input and returns an integer.
2 : Variable Initialization
int res =0;
Initialize a variable `res` to store the result integer.
3 : Variable Initialization
int sgn =1;
Initialize a variable `sgn` to store the sign of the integer (1 for positive, -1 for negative).
4 : Variable Initialization
int i =0;
Initialize an index `i` to iterate through the string.
5 : Loop Iteration
while(i < s.size() && s[i] ==' ') i++;
Skip leading whitespace characters.
6 : Conditional Check
if(i < s.size() && (s[i] =='+'|| s[i] =='-'))
Check if the next character is a sign character (`+` or `-`)
7 : Conditional Assignment
sgn = (s[i++] =='+')?1:-1;
Set the sign based on the character and increment the index `i`.
8 : Loop Iteration
while(i < s.size() && s[i] >='0'&& s[i] <='9') {
Iterate while the current character is a digit.
9 : Conditional Check
if(res > INT_MAX/10||
Check if the current `res` value is greater than the maximum integer divided by 10.
10 : Conditional Check
(res == INT_MAX/10&& ((s[i]-'0')>(INT_MAX %10))))
Check if `res` is equal to the maximum integer divided by 10 and the next digit is greater than the maximum integer modulo 10.
11 : Return Value
return (sgn >0)?INT_MAX: INT_MIN;
If overflow occurs, return `INT_MAX` for positive numbers or `INT_MIN` for negative numbers.
12 : Mathematical Operations
res = res *10+ (s[i++] -'0');
Update the `res` value by multiplying it by 10 and adding the current digit.
13 : Comment
// cout << res << " ";
A commented-out line to print the intermediate `res` value for debugging purposes.
14 : Return Value
return sgn * res;
Return the final result multiplied by the sign.
Best Case: O(n), where n is the length of the string.
Average Case: O(n), where n is the length of the string.
Worst Case: O(n), where n is the length of the string.
Description: The time complexity depends on the length of the string as we only make a single pass through it.
Best Case: O(1), since the space used is constant.
Worst Case: O(1), since we only use a few variables to store the result and current position.
Description: The space complexity is constant, O(1), as we don't use extra space for data structures.
