力扣 36 有效的数独

题意：给定一个数独的棋盘，判断其是否合法

思路：搜索遍历每一种可能结果，具体解析见代码注释

思想：数组遍历

复杂度：时间O(n²)，空间O(1)

class Solution {
    public boolean isValidSudoku(char[][] board) {
        int m = board.length;
        if(m == 0)
            return false;
        int n = board[0].length;
        
        for(int i=0;i<m;i++) {
            for(int j=0;j<n;j++) {
                // 查看每一个数字元素看是否合法
                if(board[i][j] != '.' && invalid(i, j, board)) {
                    return false;
                }
            } 
        }
        return true;
    }
    
    boolean invalid(int i, int j, char[][] board) {
        int m = board.length;
        int n = board[0].length;
        char cur = board[i][j];
        for(int z=0;z<m;z++) {
            // 查每一行是否合法
            if(z != j && board[i][z] == cur) 
                return true;
            // 查每一列是否合法
            if(z != i && board[z][j] == cur)
                return true;
            // 查每一个3元格是否合法
            int curi = i/3 * 3 + z%3;
            int curj = j/3 * 3 + z/3;
            if(curi != i && curj != j && board[curi][curj] == cur)
                return true;
        }
        return false;
    }
}