8. String to Integer (atoi)

Solution 1: Brute-Force

    def myAtoi(self, s: str) -> int:
        if not s:
            return 0
        
        lenN = len(s)
        MAX_INT, MIN_INT = 2147483647, -2147483648
        sign = 1
        decimal = 0
        idx = 0
        
        # 1. Ignore leading whitespace
        while idx < lenN and s[idx] == ' ':
            idx += 1
        
        # 2. Determine the Sign (+/-)
        if idx < lenN and s[idx] == '-':
            sign = -1
            idx +=1
        elif idx < lenN and s[idx] == '+':
            sign = 1
            idx +=1
        
        # 3. Deal with digit between ['0' - '9']
        while idx < lenN and '0' <= s[idx] and s[idx] <= '9':
            digitInt = ord(s[idx]) - ord('0')
            
            # 3.1 Detect overflow
            if (decimal > MAX_INT // 10) or (decimal == (MAX_INT // 10) and digitInt > MAX_INT % 10):
                return MAX_INT if sign == 1 else MIN_INT
            # 3.2 Calculate new decimal
            decimal = 10 * decimal + digitInt
            idx += 1
        
        return sign * decimal

Time Complexity: O(N)
Space Complexity: O(1)

Solution 2: Deterministic Finite Automaton (DFA)

Time Complexity: O(N)
Space Complexity: O(1)

Reference

https://leetcode.com/problems/string-to-integer-atoi/discuss/4654/My-simple-solution
https://leetcode.com/problems/string-to-integer-atoi/discuss/798380/Fast-and-simpler-DFA-approach-(Python-3)