Monday, December 22, 2014

Valid Sudoku (LeetCode HashMap)

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).

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