Question: Determine if a Sudoku is valid. The Sudoku board could be partially filled, where empty cells are filled with the character '.'.
A partially filled sudoku which is valid.
Idea: Brute force method. Check each row, each column, each 3*3 square. Use a set to cache the characters appeared.
Time: O(n^2). Space: O(n).
Time: O(n^2). Space: O(n).
Code:
public class Solution {
public boolean isValidSudoku(char[][] board) {
if(board.length==0||board[0].length==0)
{
return true;
}
HashSet<Character> set=new HashSet<Character>();
for(int i=0;i<board.length;i++)
{
set.clear();
for(int j=0;j<board[0].length;j++)
{
if(board[i][j]=='.')
{
continue;
}
if(set.contains(board[i][j]))
{
return false;
}
else
{
set.add(board[i][j]);
}
}
}
for(int j=0;j<board[0].length;j++)
{
set.clear();
for(int i=0;i<board.length;i++)
{
if(board[i][j]=='.')
{
continue;
}
if(set.contains(board[i][j]))
{
return false;
}
else
{
set.add(board[i][j]);
}
}
}
for(int i=0;i<board.length;i+=3)
{
for(int j=0;j<board[0].length;j+=3)
{
set.clear();
for(int k=0;k<9;k++)
{
int curI=i+k/3;
int curJ=j+k%3;
if(board[curI][curJ]=='.')
{
continue;
}
if(set.contains(board[curI][curJ]))
{
return false;
}
else
{
set.add(board[curI][curJ]);
}
}
}
}
return true;
}
}
No comments:
Post a Comment