# String to Integer (atoi)

• Solution in Python

Cases to handle

• leading white spaces in the input string have to be removed
• First non-whitespace character could be an optional '+' or '-' symbol indicating sign of the number followed by as many numerical digits as possible which is interpreted as a numeric value.
• Additional characters after those that form the integral number, should be ignored and should have no effect on the behavior of this function
• If no valid conversion could be performed, a zero value is returned.
• If the correct value is out of the range of representable values, INT_MAX (2147483647) or INT_MIN (-2147483648) is returned.

Approach #1 (Regex) [Accepted]

The regex approach uses the re module from the python standard library. We write a regular expression to match all strings that have leading white spaces followed by an optional '+' or '-' followed by digits.
We use a try-catch block to handle the condition that If no valid conversion could be performed, a zero value is returned.
Once we get the desired string, it can be converted to an integer and returned after checking for overflow conditions.

``````def myAtoi(self, str):

try:
a = int(re.match(r'\s*[\+|-]?\d*',str).group())

if a>2147483647:
return 2147483647
if a<-2147483648:
return -2147483648
return a
except:
return 0
``````

Complexity Analysis

• Time complexity : O(2n) = O(n). In the worst case each character will be visited twice. First for regex pattern matching and then for casting the string obtained by the regex to int.
• Space complexity : O(n). In the worst case (assuming all characters in the input string are numbers , we will be storing n element string in memory which we obtain as the output of the regex.

Approach #2 (character comparison) [Accepted]

The previous approach suffered from the draw back that we were visiting each character twice.
The solution can be improved upon by removing the dependency on the re module.

Mathematically - The number can be built from each digit obtained in sequence using the following formula -

``````                                     num = num *10 + digit
``````

where num is initialized to zero and digit is each numeric character obtained from the string as we read the string from left to right

``````    An Integer `1234` can be formed as shown below.
Step1: 1
Step2: 1*10 + 2 = 10 + 2 = 12
Step3: 12*10 + 3 = 120 + 3 = 123
Step4: 123*10 + 4 = 1230 + 4 = 1234
``````
``````    def myAtoi(self, str):
res = 0
str = str.lstrip()
try:
if str[0] == '+':
sign = 1
elif str[0] == '-':
sign = -1
elif 48<=ord(str[0])<=57:
sign = 1
res = res*10 + (ord(str[0])-48)
else:
return 0
for ch in str[1::]:
if 48<=ord(ch)<=57:
res=res*10+(ord(ch)-48)
else:
break

if (res*sign)>2147483647:
return 2147483647
elif (res*sign)<-2147483648:
return -2147483648
else:
return res*sign

except:
return 0
``````

Complexity Analysis

• Time complexity : O(n) . In the worst case each character will be visited once.
• Space complexity : O(1) This is a constant time algorithm as the memory usage is independent of the size of the input string.

Approach #3 (character comparison - without built-in functions) [Accepted]

The above solution can be rewritten to remove the dependency on the function str.lstrip().

We use an additional variable that helps us break out of the loop if there is a space character after numeric digits in the string but if the same space is present as a leading space in the input string we pass over to next character until we encounter a non-white space character.
The time and space complexity remains the same as Approach 2.

``````def myAtoi(self, str):
res = 0
temp = 0
temp1 = 0
sign = 1
if str == "":
return 0
try:
for ch in str:
if temp>=2:
return res
elif ch==" ":
if (temp>=1) or (temp1>0):
break

else:
pass
elif ch == "+":
temp = temp+1
sign = 1

elif ch == "-":
sign = -1
temp = temp+1
elif 48<=ord(ch)<=57:
temp1 = temp1+1
res = res*10 + (ord(ch)-48)
else:
break

sum = res*sign

if sum>2147483647:
return 2147483647
elif sum<-2147483648:
return -2147483648
else:
return sum
except:
return 0
``````

Complexity Analysis

• Time complexity : O(n) . In the worst case each character will be visited once.
• Space complexity : O(1) This is a constant time algorithm as the memory usage is independent of the size of the input string.

• ``````public static int myAtoi(String str) {
int result = 0;
boolean isSigned = false;
int i = 0;
if(str != null && str.length() > 0) {
if(str.charAt(0) == '-' || str.charAt(0) =='+') {
i++;
if(str.charAt(0) == '-') {
isSigned = true;
}
}
while(i < str.length()) {
if(str.charAt(i) == ' ') {
i++;
continue;
}
int value = (int)str.charAt(i) - 48;
if(value >= 0 && value <= 9) {
result = result * 10 + value;
} else {
return 0;
}
i++;
}
}
if(isSigned) {
result = 0 - result;
}
return result;
}``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.