[ LeetCode  ]

LeetCode 36: Valid Sudoku

本题主要考察 Hash 表集合数据结构。

题目

Determine if a 9x9 Sudoku board is valid. Only the filled cells need to be validated according to the following rules:

  1. Each row must contain the digits 1-9 without repetition.
  2. Each column must contain the digits 1-9 without repetition.
  3. Each of the 9 3x3 sub-boxes of the grid must contain the digits 1-9 without repetition.

解法

《编程珠玑》一书中第三章“数据决定程序结构”强调了数据结构对程序编写的重要性,这个题目同样如此。

思考一个问题:有两个集合 $A$ 和 $B$,要求两个集合的交集,你怎么做?这个题目是我当时一面腾讯的时候被问到的,可惜当时我太紧张,只说了最简单的暴力遍历 $O(N^2)$ 的方法。但即使是最普通的遍历,如果用 Hash 表来代替数组,时间复杂度也能迅速降到 $O(N)$,这就体现了高级数据结构的优越性。

注意数独问题中,要求每一行、每一列、每个区块都不能有重复的数字,这恰好对应集合的性质:没有重复的元素。用另一种说法可能更容易理解:“第4行的5”只能有一个,“第7列的3”只能有一个……因此,我们可以构建一个集合 $S$,其中每个元素就是“某个位置的某个数字”,它们不应该重复。

遍历一遍格子,对每个数字进行这样的处理:如果这一行这一列这一区块有过这个数字,则退出算法并返回 False;否则,把这三种情况加入到集合 $S$ 中。遍历完就可以保证 valid,可以返回 True

实现

下面是我用 Python 中 set 的实现:

class Solution:
    def isValidSudoku(self, board):
        seen = set()
        for i in range(9):
            for j in range(9):
                e = board[i][j]
                if e != '.':
                    r = e + 'in row' + str(i)
                    c = e + 'in col' + str(j)
                    b = e + 'in blk' + str(i // 3) + str(j // 3)
                    if r in seen or c in seen or b in seen:
                        return False
                    else:
                        seen.add(r)
                        seen.add(c)
                        seen.add(b)
        return True

在 Python 中对 set 执行 in 操作的搜索的平均时间复杂度为 $O(1)$,因为它的实现就是 Hash 表。这段代码的运行时间打败 94.39 %的 Python 3代码。

参考

(本文完)