问题描述
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'，当某数字在某行/列/方块中没有出现过时，value为False，出现时改为True，若读到某数时，发现其某行/列/方块记录中对应的value为True，则返回invalid。
这么做非常慢！Runtime: 384 ms, which beats 2.66% of Python submissions.
我用哈希表的初衷是这样对于一个数字可以在O(1)内寻址，然而经过男票教诲，发现明明搞个数组就可以在0(1)内寻址...
然后我就用数组的方式来记录数字的出现。申请三个9x9数组，分别记录行/列/方块中数字的出现情况。
然而这样还是挺慢的。Runtime: 104 ms, which beats 16.56% of Python submissions.
然后我去九章算法上看了参考程序，它采用的是每行/列/方块用一个set记录，读到一个数字后看相应set中是否已经存在该数字。
这种做法效率比较高。Runtime: 72 ms, which beats 89.37% of Python submissions.
得到的教训是：不要迷信和瞎用哈希表...
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
