String To Integer (atoi) Problem

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:

• 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 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.

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;
}
``````