A readable Python solution, with TC: O(n^2)


  • 0
    W

    This is a very good sample to balance in Time and Space, we can use many spaces to store mark bit, or we can use little mark bit but traverse all items many times.

    Basically, my solution used 3 matrix, each matrix has 9*9 bite. 3 matrix to store is current element has shown in row / column / group validation.

    width = 9
    
    class Solution:
        # @param board, a 9x9 2D array
        # @return a boolean
        def isValidSudoku(self, board):
          rowMatrix = self.getValidMatrix()
          columnMatrix = self.getValidMatrix()
          groupMatrix = self.getValidMatrix()
    
          if len(board) != width:
            return False
    
          for i in range(width):
            if len(board[i]) != width:
              return False
    
            for j in range(width):
              if board[i][j] == '.':
                continue
    
              cell = int(board[i][j]) - 1
              # Validate Rows
              if rowMatrix[i][cell]:
                return False
              # Validate Columns
              if columnMatrix[j][cell]:
                return False
              # Validate Groups
              if groupMatrix[(i // 3) * 3 + j //3][cell]:
                return False
    
              rowMatrix[i][cell] = True
              columnMatrix[j][cell] = True
              groupMatrix[(i // 3) * 3 + j //3][cell] = True
    
          return True
    
        def getValidMatrix(self):
          result = []
          for i in range(width):
            result.append([])
            for j in range(width):
              result[i].append(False)
          return result

  • 0
    G
    This post is deleted!

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.