O(n) Solution using unordered set


#1

int Solution::isValidSudoku(const vector &A) {
int size=A.size();
int i,j;
unordered_set sudoku;
unordered_set s;
for(i=0;i<size;i++)
{
sudoku.clear();
for(j=0;j<size;j++)
{
if(A[i][j]!=’.’)
{
if(sudoku.find(A[i][j])!=sudoku.end())
return 0;
sudoku.insert(A[i][j]);
}
}
}
for(i=0;i<size;i++)
{
sudoku.clear();
for(j=0;j<size;j++)
{
if(A[j][i]!=’.’)
{
if(sudoku.find(A[j][i])!=sudoku.end())
return 0;
sudoku.insert(A[j][i]);
}
}
}
int ik,jk,root;
root=(int)sqrt(size);
for(ik=0;ik<root;ik++)
{
sudoku.clear();
for(jk=0;jk<root;jk++)
{
sudoku.clear();
// cout<<endl;
for(i=ikroot;i<ikroot+root;i++)
{

            for(j=jk*root;j<jk*root+root;j++)
            {
                
                if(A[i][j]!='.')
                {
                    if(sudoku.find(A[i][j])!=sudoku.end())
                    {
                        // cout<<"("<<i<<","<<j<<")";
                        // cout<<"current sudoku is"<<endl;
                        // for(auto h=sudoku.cbegin();h!=sudoku.cend();h++)
                        // cout<<*h;
                        // cout<<endl;
                        return 0;
                    }
                    sudoku.insert(A[i][j]);
                }
                // cout<<"("<<i<<","<<j<<")";
            }
            // cout<<endl;
        }
        
    }
}
// int counti,countj,sq_root;
// sq_root=(int)sqrt(size);
// counti=countj=0;
// for(i=counti*sq_root-1;i<counti*sq_root-1+sq_root&&i<size;i++)
// {
//     countj=0;
//       for(j=countj*sq_root-1;j<countj*sq_root-1+sq_root&&j<size;j++)
//       cout<<"value of i, j is"<<i<<","<<j;
//       countj++;
//     cout<<endl;
// }
return 1;

}