[LeetCode] 65. Valid Number

Problem : https://leetcode.com/problems/valid-number/

Not hard but annoying.  Use FSM to check if character is allowed in the current state.

class Solution:
    def isNumber(self, s: str) -> bool:
        
        state = 'sign'
        
        for w in s:   
            if state == 'sign':
                if w in '+-':
                    state = 'integer_start'
                    continue
                
                if w.isdigit():
                    state = 'integer'
                    continue
                
                if w == '.':
                    state = 'decimal_start'
                    continue
            
                return False
            
            if state == 'integer_start':
                if w.isdigit():
                    state = 'integer'
                    continue
                
                if w == '.':
                    state = 'decimal_start'
                    continue
                       
                return False
            
            if state == 'integer':
                
                if w.isdigit():
                    continue
                    
                if w in 'eE':
                    state = 'sign_e'
                    continue
                
                if w == '.':
                    state = 'decimal'
                    continue
                
                return False
            
            if state == 'decimal_start':
                if w.isdigit():
                    state = 'decimal'
                    continue
                
                return False
            
            if state == 'decimal':
                if w.isdigit():
                    continue
                
                if w in 'eE':
                    state = 'sign_e'
                    continue
                
                return False
                        
            
            if state == 'sign_e':
                
                if w in '+-':
                    state = 'num_e_start'
                    continue
                
                if w.isdigit():
                    state = 'num_e'
                    continue
                    
                return False
            
            if state == 'num_e_start':
                if w.isdigit():
                    state = 'num_e'
                    continue
                
                return False
            
            if state == 'num_e':
                if w.isdigit():
                    continue
                
                return False
            
        if state == 'integer_start':
            return False
                    
        if state == 'decimal_start':
            return False
        
        if state == 'num_e_start':
            return False
        
        if state == 'sign_e':
            return False
        
        
        return True

Edited on 05/15/2021. Refactor FSM code.

[LeetCode] 59. Spiral Matrix II

Problem : https://leetcode.com/problems/spiral-matrix-ii/

Use FSM to simulate the process for filling numbers. Be careful, it must break the loop immediately when i >= n * n.

class Solution(object):
    def generateMatrix(self, n):
        """
        :type n: int
        :rtype: List[List[int]]
        """
        
        board = [[0] * n for _ in range(n)]
        
        i = 1
        board[0][0] = 1
        
        y, x = 0, 0
        padding_y, padding_x = 0, 0
        
        state = 'right'
        
        while True:
            if state == 'right':
                if x + 1 >= n - padding_x:
                    state = 'down'
                else:
                    x += 1
                    i += 1
                    board[y][x] = i
            
            elif state == 'down':
                if y + 1 >= n - padding_y:
                    state = 'left'
                else:
                    y += 1
                    i += 1
                    board[y][x] = i
                    
            elif state == 'left':
                if x - 1 < padding_x:
                    state = 'up'
                    padding_y += 1
                else:
                    x -= 1
                    i += 1
                    board[y][x] = i
                    
            elif state == 'up':
                if y - 1 < padding_y:
                    state = 'right'
                    padding_x +=1 
                else:
                    y -= 1
                    i += 1
                    board[y][x] = i
                    
            if i >= n * n:
                break
                    
        return board

[LeetCode] 54. Spiral Matrix

Problem : https://leetcode.com/problems/spiral-matrix/

Use FSM to simulate the process of iterating element and put the visited element to result array.

Stop iterating when result array size equals to the matrix size. 

Remember to handle the edge case when input matrix is empty.

Time Complexity : O ( M * N )

Space Complexity: O ( M * N )

class Solution:
    def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
        ROW = len(matrix)
        COLUMN = len(matrix[0])
        
        nextPos = {'right': (0, 1), 'down': (1, 0), 'left': (0, -1), 'up': (-1, 0)}
        nextDir = {'right': 'down', 'down': 'left', 'left': 'up', 'up': 'right'}
        
        y, x = 0, -1
        direction = 'right'
        
        result = []
        visited = defaultdict(bool)
        
        while len(result) < ROW * COLUMN:
            ny, nx = y + nextPos[direction][0], x + nextPos[direction][1]
            
            if 0 <= ny < ROW and 0 <= nx < COLUMN and not visited[ny,nx]:
                visited[ny, nx] = True
                result.append(matrix[ny][nx])
                y, x = ny, nx
            else:
                direction = nextDir[direction]
            
        return result

Edited on 09/16/2021. Refactor by using dictionary to save next position to move forward and next direction when need to make a turn.

[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