Solutions to JZ 67 (same as LeetCode 8 String to Integer (atoi)).
JZ 67 | LeetCode 8
String to integer (Medium). [Nowcoder link] [LeetCode link]
We have to deal with “leading whitespace” (delete it), “- + sign” (keep it), “non-digit character” (return), “digits” (convert character to integer by ASCII and then combine the digits). For the integer, we also need to clamp it if the integer is out of the 32-bit signed integer range. The final result should be an integer.
Specifically, we combine the digits by the formula: res = 10 * res + x. We need to consider two scenarios of being out of range [-2147483648, 2147483647]: 1) 10 * res > 2147483650, out of boundary, i.e. res > 214748364, 2) 10 * res + x = 2147483648 or 2147483649, i.e. res = 214748364, x > 7. Let’s define boundary = 2147483647 // 10 = 214748364, the two scenarios can be written as: 1) res > boundary, 2) res = boundary, x > 7.
The time complexity is O(n), and the space complexity is O(n).
class Solution:
def StrToInt(self , s: str) -> int:
s = s.strip() # delete white space
if not s:
return 0
res, i, sign = 0,1,1
upper, lower, boundary = 2 ** 31 - 1, -2 ** 31, 2 ** 31 //10
if s[0] == '-':
sign = -1
elif s[0] != '+':
i = 0 # it has to be digit char or non-digit char from index 0
for char in s[i:]:
if not '0' <= char <= '9': # non-digit character
break
if res > boundary or (res == boundary and char > '7'):
return upper if sign == 1 else lower # deal with scenarios of being out of range
res = 10 * res + ord(char) - ord('0') # join digits
return sign * res
