36. Valid Sudoku

O(1) time O(1) space

from copy import deepcopy
class Solution:
    def isValidSudoku(self, board: List[List[str]]) -> bool:
        v = [[False] * 10 for _ in range(9)]
        h = [[False] * 10 for _ in range(9)]
        b = [[False] * 10 for _ in range(9)]
        # v = [[False] * 10 for _ in range(9)]
        # h, b = deepcopy(v), deepcopy(v)
        for r in range(9):
            for c in range(9):
                x = board[r][c]
                if x != '.':
                    x = int(x) # 巧妙！
                    if v[c][x] or h[r][x] or b[r // 3 * 3 + c // 3][x]:
                        return False
                    v[c][x] = h[r][x] = b[r // 3 * 3 + c // 3][x] = True
        return True

用bitset替代hashtable遍历找重复即可

class Solution {
public:
    bool isValidSudoku(vector<vector<char>>& board) {
        vector<bitset<9>> h(9), v(9), s(9);
        for (int r(0); r < 9; ++r) {
            for (int c(0); c < 9; ++c) {
                if (board[r][c] == '.')
                    continue;
                int x = board[r][c] - '1';
                if (h[r][x] || v[c][x] || s[r / 3 * 3 + c / 3][x]) return false;
                h[r][x] = v[c][x] = s[r / 3 * 3 + c / 3][x] = true;
            }
        }
        return true;
    }
};