Leetcode 8 Solution

This article provides solution to leetcode question 8 (string-to-integer-atoi)
Categories:
Tags:
Access this page by simply typing in "lcs 8" in your browser address bar if you have bunnylol configured.

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