[LeetCode] 8. String to Integer (atoi)

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

This problem is similar to the #7. Need to always check if overflow when append digit.
Meanwhile, it's better to use state machine to handle plus / minus sign and non-digit characters.

Time complexity =  O( N ),  N = len(s)
Space complexity =  O( N ),  N = number of valid digits 

class Solution:
    def myAtoi(self, s: str) -> int:
        MAX_INT = 2 ** 31 - 1
        MIN_INT = -2 ** 31
        
        sign = 1
        state = 'space'
        num = 0
        
        i = 0
        while i < len(s):
            if state == 'space':
                if s[i] == ' ':
                    i += 1
                else:
                    state = 'sign'
            elif state == 'sign':
                if s[i] == '+':
                    i += 1
                    state = 'digit'
                elif s[i] == '-':
                    sign = -1
                    i += 1
                    state = 'digit'
                elif s[i].isdigit():
                    state = 'digit'
                else:
                    # illegal number
                    break
            elif state == 'digit':
                if s[i].isdigit():
                    remainder = int(s[i]) * sign
                    
                    if num > MAX_INT // 10 or \
                       (num == MAX_INT // 10 and remainder >= MAX_INT % 10):
                        num = MAX_INT
                        break
                    
                    if num < MIN_INT // 10 or \
                       (num == (MIN_INT - (MIN_INT % -10)) // 10 and remainder <= MIN_INT % -10):
                        num = MIN_INT
                        break
                    
                    num = num * 10 + remainder
                    i += 1
                else:
                    # stop parsing when the encountered character is not digit
                    break
            
        return num