問題描述

Determine if a Sudoku is valid, according to: Sudoku Puzzles - The Rules.
The Sudoku board could be partially filled, where empty cells are filled with the character '.'.

A partially filled sudoku which is valid.

Note: A valid Sudoku board (partially filled) is not necessarily solvable. Only the filled cells need to be validated.

思路分析

這是一道Easy題，我一開始蠢了一下，想著用哈希表（Python里的dict）來提高速度，key值為'1', '2', ..., '9'，當(dāng)某數(shù)字在某行/列/方塊中沒有出現(xiàn)過時(shí)，value為False，出現(xiàn)時(shí)改為True，若讀到某數(shù)時(shí)，發(fā)現(xiàn)其某行/列/方塊記錄中對(duì)應(yīng)的value為True，則返回invalid。
這么做非常慢！Runtime: 384 ms, which beats 2.66% of Python submissions.
我用哈希表的初衷是這樣對(duì)于一個(gè)數(shù)字可以在O(1)內(nèi)尋址，然而經(jīng)過男票教誨，發(fā)現(xiàn)明明搞個(gè)數(shù)組就可以在0(1)內(nèi)尋址...
然后我就用數(shù)組的方式來記錄數(shù)字的出現(xiàn)。申請(qǐng)三個(gè)9x9數(shù)組，分別記錄行/列/方塊中數(shù)字的出現(xiàn)情況。
然而這樣還是挺慢的。Runtime: 104 ms, which beats 16.56% of Python submissions.
然后我去九章算法上看了參考程序，它采用的是每行/列/方塊用一個(gè)set記錄，讀到一個(gè)數(shù)字后看相應(yīng)set中是否已經(jīng)存在該數(shù)字。
這種做法效率比較高。Runtime: 72 ms, which beats 89.37% of Python submissions.

得到的教訓(xùn)是：不要迷信和瞎用哈希表...

AC代碼

class Solution(object):
    def isValidSudoku(self, board):
        """
        :type board: List[List[str]]
        :rtype: bool
        """
        line_set = [set([]) for j in range(9)]
        row_set = [set([]) for j in range(9)]
        square_set = [set([]) for j in range(9)]

        for i in range(9):
            for j in range(9):
                item = board[i][j]
                if item == '.':
                    continue
                if item in line_set[i] or item in row_set[j] or item in square_set[i/3 * 3 + j/3]:
                    return False
                else:
                    line_set[i].add(item)
                    row_set[j].add(item)
                    square_set[i/3 * 3 + j/3].add(item)
        return True