36. Valid Sudoku

Method 1 - use string

use string, to store

row, col, box's used value in set

simple way, but it's so slow... 12ms

/*
    time complexity: O(1), space complexity: O(1)
*/
class Solution {
    public boolean isValidSudoku(char[][] board) {
        Set<String> used = new HashSet<>();
        
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                char num = board[i][j];
                if (num != '.') {
                     if (!used.add(num + "row" + i) ||
                         !used.add(num + "col" + j) ||
                         !used.add(num + "box" + i/3 + "-" + j/3)) {
                         return false;
                     }
                }
            }
        }
        return true;
    }
}

Method 2 - use 3 set

2ms

the key is

char boxVal = board[(i/3)*3 + j/3][(i%3)*3 + j%3];

class Solution {
    public boolean isValidSudoku(char[][] board) {

        for (int i = 0; i < 9; i++) {
            Set<Character> row = new HashSet<>();
            Set<Character> col = new HashSet<>();
            Set<Character> box = new HashSet<>();
            
            for (int j = 0; j < 9; j++) {
                char rowVal = board[i][j];
                if (rowVal != '.' && !row.add(rowVal)) return false;
                
                char colVal = board[j][i];
                if (colVal != '.' && !col.add(colVal)) return false;

                char boxVal = board[(i/3)*3 + j/3][(i%3)*3 + j%3];
                if (boxVal != '.' && !box.add(boxVal)) return false;

            }
        }
        return true;
    }
}

```java
class Solution {
    public boolean isValidSudoku(char[][] board) {
        Set<Character>[] rowSet = new HashSet[9];
        Set<Character>[] colSet = new HashSet[9];
        Set<Character>[] boxSet = new HashSet[9];
        for (int i = 0; i < 9; i++) {
            rowSet[i] = new HashSet();
            colSet[i] = new HashSet();
            boxSet[i] = new HashSet();
        }

        for (int r = 0; r < 9; r++) {
            for (int c = 0; c < 9; c++) {
                char val = board[r][c];
                if (val == '.') {
                    continue;
                }
                if (rowSet[r].contains(val)) {
                    return false;
                }
                rowSet[r].add(val);

                if (colSet[c].contains(val)) {
                    return false;
                }
                colSet[c].add(val);

                int boxIdx = (r/3)*3 + c/3;
                if (boxSet[boxIdx].contains(val)) {
                    return false;
                }
                boxSet[boxIdx].add(val);
            }
        }
        return true;
    }
}

/**
T: O(n^2), n=9
S: O(n^2)

 */
```

Method 3 - use bitwise operator

class Solution {
    public boolean isValidSudoku(char[][] board) {
        int[] row = new int[9];
        int[] col = new int[9];
        int[] box = new int[9];
        int idx = 0;
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                char num = board[i][j];
                int boxIndex = (i/3)*3 + j/3;
                
                if (num != '.') {
                    idx = 1 << (num - '0'); // 左移（1~9）意思就是用9個位元去存
                
                    if ((row[i] & idx) > 0 || // > 0代表有值, 沒值應該出來是 0 (default 0)
                        (col[j] & idx) > 0 ||
                        (box[boxIndex] & idx) > 0) { //用＆去判斷是否存在
                        return false;
                    }
                    row[i] |= idx; // 紀錄值
                    col[j] |= idx;
                    box[boxIndex] |= idx;
                }

            }
        }
        return true;
    }
}