[−][src]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 } }