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

  • 0

    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] == '.':
              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):
            for j in range(width):
          return result

  • 0
    This post is deleted!

Log in to reply

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