emma.wang
BAN USERboolean isValidAns(int[][] sudoku){
//Check the correctness for each row and column
for (int i = 0; i< sudoku.length; i++){
HashMap<Integer, Boolean> row = new HashMap<Integer,Boolean>();
HashMap<Integer, Boolean> column = new HashMap<Integer,Boolean>();
for (int j = 0; j< sudoku.length; j++){
if( row.get (sudoku[i][j]) | | column.get( sudoku[j][i])){
return false;
}else{
row.put( sudoku[i][j], true);
column.put(sudoku[j][i], true);
}
}
}
return true;
}
public void findWords(char[][] m, int i, int j, LinkedList<char> path){
if( IsWord( path.toString + m[i][j])){
System.out.println( path.toString + m[i][j]) );
}
if ( IsPrefix( path.toString + m[i][j]) ){
path.add( m[i][j] );
if ( ! path.contains( m[i-1][j]) ){
findWords( m, i-1, j, path);
}
if ( ! path.contains( m[i+1][j]) ){
findWords( m, i+1, j, path);
}
if ( ! path.contains( m[i][j-1]) ){
findWords( m, i, j-1, path);
}
if ( ! path.contains( m[i][j+1]) ){
findWords( m, i, j+1, path);
}
// Start a new search
LinkedList<char> newPath = new LinkedList<char>();
newPath.add( m[i][j] );
findWords( m, i-1, j, newPath);
findWords( m, i+1, j, newPath);
findWords( m, i1, j-1, newPath);
findWords( m, i, j+1, newPath);
}
The general idea makes sense but it would give wrong answer if we only consider the relative order of element greater/less than root...
- emma.wang July 28, 2012e.g. {10 12 13 11 4 2 6 } and {10 12 11 13 4 6 2} would construct the same BST, but the relative order is different...
To make this right, we should not only consider the root, but each element as well, but it would be O(n^2)....