Leetcode 8 Solution

This article provides solution to leetcode question 8 (string-to-integer-atoi)

https://leetcode.com/problems/string-to-integer-atoi

Thinking Process

This question requires you to be careful. First of all, we need to understand all the cases the question asks us to support:

  • Empty string means 0.
  • There could be leading empty spaces, but no leading chars other than +, -, 0, 1, 2, 3, 4, 5, 6, 7, 9.
  • After the sign, the digits have to come right after.
  • There could be other chars at the end, ignore them.

Based on the above observations, I implemented the algorithm as shown in the last section.

Time & Space Complexity

Assuming N is the size of the string

  • Time complexity: O(N)
  • Space complexity: O(1)

Solution

class Solution(object): def myAtoi(self, s): """ :type s: str :rtype: int """ s = s.strip()
if len(s) == 0: return 0
negative = False i = 0
if s[0] == '+': i += 1 elif s[0] == '-': i += 1 negative = True
num = 0 while i < len(s) and '0' <= s[i] <= '9': num = 10 * num + int(s[i]) i += 1
if not negative and num > 2**31 - 1: return 2**31 - 1 elif negative and -num < -2**31: return -2**31
return num if not negative else -num