Solution For String To Integer Atoi
Problem Statement:
Implement the ‘myAtoi(string s)’ function, which converts a string to a 32-bit signed integer (similar to C/C++’s atoi function).
The algorithm should do the following:
1. Ignore initial white spaces
2. Check for an optional sign (+/-)
3. Read in digits until the next non-digit character
4. Convert the digits to an integer, and return the integer value.
If the algorithm cannot perform the conversion, it returns 0.
Function Signature:
int myAtoi(string s)
Solution:
We will follow the steps as given in the problem statement:
1. Ignore initial white spaces: We loop until we encounter a non-white space character.
2. Check for an optional sign (+/-): If we encounter a ‘-‘ sign, we set the ‘negative’ flag. If we encounter a ‘+’ sign or no sign, we leave the ‘negative’ flag unset.
3. Read in digits until the next non-digit character: We loop through the input until we encounter a non-digit character. We keep track of the sum of digits accumulated so far by multiplying the earlier sum by 10 and adding the value of the current digit to the result.
4. Convert the digits to an integer, and return the integer value: We return the integer value after applying the sign.
Note that we also need to make sure that the value does not overflow the 32-bit signed integer range [-2^31,2^31 – 1].
Code:
class Solution {
public:
int myAtoi(string s) {
int i = 0, n = s.size(), sign = 1;
long long int res = 0;
// Step 1: Ignore initial white spaces
while (i < n && s[i] == ‘ ‘)
i++;
// Step 2: Check for an optional sign (+/-)
if (i < n && s[i] == ‘-‘) {
sign = -1;
i++;
} else if (i < n && s[i] == ‘+’) {
i++;
}
// Step 3: Read in digits until the next non-digit character
while (i < n && isdigit(s[i])) {
res = res * 10 + s[i] – ‘0’;
i++;
if (res > INT_MAX) // check for overflow
return (sign == -1) ? INT_MIN : INT_MAX;
}
// Step 4: Convert the digits to an integer, and return the integer value
return sign * res;
}
};
Time Complexity: O(n), where n is the length of the input string.
Space Complexity: O(1). We use constant extra space.
Step by Step Implementation For String To Integer Atoi
public class Solution { public int myAtoi(String str) { //check for null or empty string if(str == null || str.isEmpty()) return 0; //trim leading and trailing whitespaces str = str.trim(); //check for empty string after trimming if(str.isEmpty()) return 0; //check for invalid input if(!str.matches("[\\+\\-]?\\d+")) return 0; //convert string to integer int result = 0; try { result = Integer.parseInt(str); } catch(NumberFormatException e) { //check for overflow if(str.charAt(0) == '-') return Integer.MIN_VALUE; else return Integer.MAX_VALUE; } return result; } }
def myAtoi(s): # remove leading and trailing whitespace s = s.strip() # check for empty string if not s: return 0 # determine sign sign = -1 if s[0] == '-' else 1 # set starting index for conversion based on sign start = 1 if sign == -1 else 0 # initialize result res = 0 # convert string to integer for i in range(start, len(s)): # check for valid characters if not s[i].isdigit(): break # convert character to integer and add to result res = res * 10 + int(s[i]) # handle integer overflow return max(-2147483648, min(sign * res, 2147483647))
/** * @param {string} str * @return {number} */ var myAtoi = function(str) { // remove whitespace from beginning of string str = str.trim(); // base case: empty string if (str.length === 0) { return 0; } // set sign to positive by default let sign = 1; // check if first character is a negative sign if (str[0] === '-') { sign = -1; // remove the negative sign from the string str = str.substring(1); } // check if first character is a positive sign if (str[0] === '+') { // remove the positive sign from the string str = str.substring(1); } // base case: first character is not a digit if (isNaN(str[0])) { return 0; } // initialize result as 0 let result = 0; // iterate through string, converting each digit character to a number // and adding it to the result for (let i = 0; i < str.length; i++) { // base case: current character is not a digit if (isNaN(str[i])) { // stop iterating break; } // convert current digit character to number and add to result result = (result * 10) + Number(str[i]); } // return final result, taking sign into account return sign * result; };
class Solution { public: int myAtoi(string str) { int res = 0, sign = 1, i = 0; // handle empty string if (str.empty()) return 0; // handle leading spaces while (str[i] == ' ') ++i; // handle sign if (str[i] == '+' || str[i] == '-') { sign = (str[i++] == '+') ? 1 : -1; } // convert number and avoid overflow while (i < str.size()) { if (str[i] < '0' || str[i] > '9') break; if (res > INT_MAX / 10 || (res == INT_MAX / 10 && str[i] - '0' > 7)) { return (sign == 1) ? INT_MAX : INT_MIN; } res = 10 * res + (str[i++] - '0'); } return sign * res; } };
using System; public class Solution { public int Atoi(string str) { // check for null or empty string if (string.IsNullOrEmpty(str)) { return 0; } // remove leading and trailing whitespaces str = str.Trim(); // check for empty string again if (string.IsNullOrEmpty(str)) { return 0; } // check for sign int sign = 1; if (str[0] == '+') { str = str.Substring(1); } else if (str[0] == '-') { sign = -1; str = str.Substring(1); } // check for empty string after removing sign if (string.IsNullOrEmpty(str)) { return 0; } // check for invalid characters foreach (char c in str) { if (!Char.IsDigit(c)) { return 0; } } // convert string to integer int result = 0; foreach (char c in str) { result = result * 10 + (c - '0'); } // apply sign return sign * result; } }