Function leetcode_for_rust::cd0036_valid_sudoku::is_valid_sudoku

pub fn is_valid_sudoku(board: Vec<Vec<char>>) -> bool

Solutions

Approach 1: DFS

• Time complexity:

• Space complexity:

• Runtime: 4 ms

• Memory: 2.5 MB

impl Solution {
    pub fn is_valid_sudoku(board: Vec<Vec<char>>) -> bool {
        // 快速检索第i, j列, 第k宫的数字是否被占用
        let mut line   = [[false; 9]; 9]; // j
        let mut column = [[false; 9]; 9]; // i
        let mut ceil   = [[false; 9]; 9]; // k
        let mut origin = [[false; 9]; 9]; // 原始数字位置
        // 初始化
        for row in 0..9 {
            for col in 0..9 {
                let num = match board[row][col].to_digit(10) {
                    Some(n) => (n - 1) as usize,
                    None    => continue
                };

                if line[row][num] || column[col][num] ||ceil[Self::ceil_k((row, col))][num] { return false; }
                line[row][num]   = true;
                column[col][num] = true;
                origin[row][col] = true;
                ceil[Self::ceil_k((row, col))][num] = true;
            }
        }
        true
    }

    // 求出pos属于第几个ceil
    fn ceil_k(pos: (usize, usize)) -> usize {
        (pos.0 / 3) * 3 + pos.1 / 3
    }
}

Approach 2: DFS

• Time complexity:

• Space complexity:

• Runtime: 5 ms

• Memory: 2.5 MB

impl Solution {
    pub fn is_valid_sudoku(board: Vec<Vec<char>>) -> bool {
        let mut table = vec![false; 9];

        Solution::check_row(&board, &mut table) &&
        Solution::check_col(&board, &mut table) &&
        Solution::check_block(&board, &mut table)
    }

    pub fn check_row(board: &Vec<Vec<char>>, table: &mut Vec<bool>) -> bool {
        // check row
        for row in board.iter() {
            for pos in 0..9 { table[pos] = false; }
            for col in row {
                match col.to_digit(10) {
                    Some(n) => {
                        if table[(n-1) as usize] { return false; }
                        table[(n-1) as usize] = true;
                    },
                    None => continue,
                }
            }
        }
        true
    }

    pub fn check_col(board: &Vec<Vec<char>>, table: &mut Vec<bool>) -> bool {
        // check col
        for col in 0..9 {
            for pos in 0..9 { table[pos] = false; }
            for row in board.iter() {
                match row[col].to_digit(10) {
                    Some(n) => {
                        if table[(n-1) as usize] { return false; }
                        table[(n-1) as usize] = true;
                    },
                    None => continue,
                }
            }
        }
        true
    }

    pub fn check_block(board: &Vec<Vec<char>>, table: &mut Vec<bool>) -> bool {
        // check 3 * 3 block
        for i in 0..3 {
            for j in 0..3 {
                for pos in 0..9 { table[pos] = false; }
                for row in 3 * i .. 3 * (i + 1) {
                    for col in 3 * j .. 3 * (j + 1) {
                        match board[row][col].to_digit(10) {
                            Some(n) => {
                                if table[(n-1) as usize] { return false; }
                                table[(n-1) as usize] = true;
                            },
                            None => continue,
                        }
                    }
                }
            }
        }
        true
    }
}