|
| 1 | +packagemedium; |
| 2 | + |
| 3 | +publicclassWordSearch { |
| 4 | +//I made it this time, completely by myself! Cheers! This let me completely understand backtracking! |
| 5 | +publicbooleanexist(char[][]board,Stringword) { |
| 6 | +intm =board.length,n =board[0].length; |
| 7 | +for(inti =0;i <m;i++){ |
| 8 | +for(intj =0;j <n;j++){ |
| 9 | +boolean[][]visited =newboolean[m][n]; |
| 10 | +if(dfs(board,visited,i,j,word,0))returntrue; |
| 11 | + } |
| 12 | + } |
| 13 | +returnfalse; |
| 14 | + } |
| 15 | + |
| 16 | +finalint[]dirs =newint[]{0,1,0,-1,0}; |
| 17 | + |
| 18 | +booleandfs(char[][]board,boolean[][]visited,introw,intcol,Stringword,intindex){ |
| 19 | +if(index >=word.length() ||word.charAt(index) !=board[row][col])returnfalse; |
| 20 | +elseif(index ==word.length()-1 &&word.charAt(index) ==board[row][col]) { |
| 21 | +visited[row][col] =true; |
| 22 | +returntrue; |
| 23 | + } |
| 24 | +visited[row][col] =true;//set it to true for this case |
| 25 | +booleanresult =false; |
| 26 | +for(inti =0;i <4;i++){ |
| 27 | +intnextRow =row+dirs[i]; |
| 28 | +intnextCol =col+dirs[i+1]; |
| 29 | +if(nextRow <0 ||nextRow >=board.length ||nextCol <0 ||nextCol >=board[0].length ||visited[nextRow][nextCol])continue; |
| 30 | +result =dfs(board,visited,nextRow,nextCol,word,index+1); |
| 31 | +if(result)returnresult; |
| 32 | +elsevisited[nextRow][nextCol] =false;//set it back to false if this road doesn't work to allow it for other paths, this is backtracking!!! |
| 33 | + } |
| 34 | +returnresult; |
| 35 | + } |
| 36 | + |
| 37 | +publicstaticvoidmain(String...strings){ |
| 38 | +WordSearchtest =newWordSearch(); |
| 39 | +// char[][] board = new char[][]{ |
| 40 | +// {'A','B','C','E'}, |
| 41 | +// {'S','F','C','S'}, |
| 42 | +// {'A','D','E','E'}, |
| 43 | +// }; |
| 44 | +// String word = "ABCCED"; |
| 45 | +// String word = "SEE"; |
| 46 | +// String word = "ABCD"; |
| 47 | + |
| 48 | +// char[][] board = new char[][]{ |
| 49 | +// {'a','a'}, |
| 50 | +// }; |
| 51 | +// String word = "aaa"; |
| 52 | + |
| 53 | +char[][]board =newchar[][]{ |
| 54 | + {'A','B','C','E'}, |
| 55 | + {'S','F','E','S'}, |
| 56 | + {'A','D','E','E'}, |
| 57 | + }; |
| 58 | +Stringword ="ABCEFSADEESE"; |
| 59 | +System.out.println(test.exist(board,word)); |
| 60 | + } |
| 61 | +} |