Difficulty – Medium
String To Integer (atoi) Problem: 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 for myAtoi(string s) is as follows:
- Read in and ignore any leading whitespace.
- Check if the next character (if not already at the end of the string) is ‘-‘ or ‘+’. Read this character in if it is either. This determines if the final result is negative or positive respectively. Assume the result is positive if neither is present.
- Read in next the characters until the next non-digit character or the end of the input is reached. The rest of the string is ignored.
- Convert these digits into an integer (i.e. “123” -> 123, “0032” -> 32). If no digits were read, then the integer is 0. Change the sign as necessary (from step 2).
- If the integer is out of the 32-bit signed integer range [-231, 231 – 1], then clamp the integer so that it remains in the range. Specifically, integers less than -231 should be clamped to -231, and integers greater than 231 – 1 should be clamped to 231 – 1.
- Return the integer as the final result.
Only the space character ‘ ‘ is considered a whitespace character.
Do not ignore any characters other than the leading whitespace or the rest of the string after the digits.
Example 1:
Input: s = “42”
Output: 42
Explanation: The underlined characters are what is read in, 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)
The parsed integer is 42.
Since 42 is in the range [-231, 231 – 1], the final result is 42.
Example 2:
Input: s = ” -42″
Output: -42
Explanation:
Step 1: ” -42″ (leading whitespace is read and ignored)
Step 2: ” -42″ (‘-‘ is read, so the result should be negative)
Step 3: ” -42″ (“42” is read in)
The parsed integer is -42.
Since -42 is in the range [-231, 231 – 1], the final result is -42.
Example 3:
Input: s = “4193 with words”
Output: 4193
Explanation:
Step 1: “4193 with words” (no characters read because there is no leading whitespace)
Step 2: “4193 with words” (no characters read because there is neither a ‘-‘ nor ‘+’)
Step 3: “4193 with words” (“4193” is read in; reading stops because the next character is a non-digit)
The parsed integer is 4193.
Since 4193 is in the range [-231, 231 – 1], the final result is 4193.
Table of Contents
String To Integer (atoi) Problem Solution
Problem solution in Python
class Solution:
def validCharacter(self, ch):
return ord('0') <= ord(ch) <= ord('9')
def myAtoi(self, s: str) -> int:
l = list(s)
# remove whitespace
while l and l[0] == " ":
l.pop(0)
# specify sign
sign = 1
if l and l[0] == '+':
l.pop(0)
sign = 1
elif l and l[0] == '-':
l.pop(0)
sign = -1
buf = ""
while l and self.validCharacter(l[0]):
buf += l.pop(0)
result = 0
for i in buf:
num = ord(i) - ord('0')
result = result* 10 + num
result *= sign # add sign
if result > 2 ** 31 - 1:
return 2 ** 31 - 1
elif result < -(2 ** 31):
return -(2 ** 31)
else:
return result
Problem solution in Java
int start = 0, sign = 1;
long res = 0;
while(start < s.length() && s.charAt(start) == ' ') {
start++;
}
if(start < s.length() && s.charAt(start) == '+') {
start++;
} else if(start < s.length() && s.charAt(start) == '-') {
sign = -1;
start++;
}
while(start < s.length()) {
if(!Character.isDigit(s.charAt(start))) break;
res *= 10;
res += s.charAt(start) - '0';
if(res > Integer.MAX_VALUE) {
if(sign == 1) return Integer.MAX_VALUE;
return Integer.MIN_VALUE;
}
start++;
}
return (int) res * sign;
Problem solution in C++
class Solution {
public:
int myAtoi(string str) {
long long ans =0;
bool isNeg = false;
int i=0;
while(str[i]==' ')
i++;
if(str[i]=='-'){
isNeg = true;
i++;
}
else if(str[i]=='+'){
isNeg = false;
i++;
}
while(str[i]=='0')
i++;
int end=0;
for( end=i;end<str.size();end++){
if(str[end]>'9'||str[end]<'0')
break;
}
if(end-i>12){
if(isNeg)
return INT_MIN;
else return INT_MAX;
}
for(int j=i;j<str.size();j++){
if(str[j]>'9'||str[j]<'0')
break;
ans = 10*ans + str[j]-'0';
}
if(isNeg)
return (INT_MIN>-ans?INT_MIN:-ans);
else
return (INT_MAX>ans?ans:INT_MAX);
}
};
Problem solution in C
int myAtoi(char *str) {
int flag = 1;
long res = 0;
if (str == NULL) return 0;
while (*str == ' ' || *str == '\t') ++str;
if (str == NULL) return 0;
if (*str != '-' && *str != '+' && (*str < '0' || *str >'9')) return 0;
if (*str == '-') {flag = -1;++str;}
else if (*str == '+') {flag = 1; ++str;}
if (str == NULL) return 0;
int cnt = 0;
while(*str) {
if (*str < '0' || *str >'9') break;
res = res * 10 + *str - 0x30;
++str;
++cnt;
}
if (cnt > 10) return flag == 1 ? INT_MAX : INT_MIN;
res *= flag;
if (res > INT_MAX) return INT_MAX;
if (res < INT_MIN) return INT_MIN;
return (int)res;
}