Word Search

 1 public class WordSearch {
 2     
 3     public static void main(String[] args) {
 4         
 5     }
 6 
 7     public boolean DFS(char[][] board,int i, int j, String word,  boolean [][]visited) {
 8         
 9         if( word == null || word.equals("") )
10                 return true;
11 
12         if( word.length() == 1 && word.charAt(0) == board[i][j] )
13         {
14         //        System.out.println(true);    
15                 return true;
16         }
17         if( word.length() == 1 && word.charAt(0) != board[i][j] )
18                 return false;
19         int x = 0 , y = 0;
20         String subStr = word.substring(1);
21 
22         visited[i][j] = true;
23 
24         if( board[i][j] != word.charAt(0) )
25         {
26             visited[i][j] = false;
27             return false;
28         }
29 
30         //up
31         x = i - 1;
32         y = j;
33         if( x >= 0  && visited[x][y] == false)
34         {
35             if ( DFS(board, x, y, word.substring(1), visited) )
36                     return true;
37         }
38         //down
39         x = i + 1;
40         y = j;
41         if( x  < board.length && visited[x][y] == false)
42         {
43             if ( DFS(board, x, y, word.substring(1), visited) )
44                     return true;
45         }
46         //left
47         x = i;
48         y = j - 1;
49         if( y >= 0  && visited[x][y] == false)
50         {
51             if ( DFS(board, x, y, word.substring(1), visited) )
52                 return true;
53         }
54         //right
55         x = i;
56         y = j + 1;
57         if( y < board[0].length && visited[x][y] == false)
58         {
59             if ( DFS(board, x, y, word.substring(1), visited) )
60                 return true;
61         }
62         visited[i][j] = false;
63         return false;
64     }
65     // Accepted
66       public boolean exist(char[][] board, String word) {
67          
68           boolean [][]visited = new boolean[board.length][board[0].length];
69             for(int i = 0 ; i < board.length; i++ )
70             {
71 
72                 for(int j = 0 ; j < board[0].length; j++ )
73                 {
74                     if(  DFS(board, i , j, word, visited) )
75                             return true;
76                 }
77             }
78             return false;
79         }
80 }