Leetcode 79.

Version 1

Although the backtracking method of this version is based on the backtracking algorithm template I summarized, the time complexity and space complexity are a bit high. 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
class Solution {
    private static final int[][] direction = {{0,1},{0,-1},{-1,0},{1,0}};
    public boolean exist(char[][] board, String word) {       
       if (word == null || word.length() == 0) {
         return true;
       }
       if (board == null || board.length == 0 || board[0].length == 0) {
         return false;
       }
       
       StringBuilder sb = new StringBuilder();
       List<String> ans = new ArrayList<>();
       boolean[][] visited = new boolean[board.length][board[0].length];
       int wordLength = word.length();
       for(int i = 0; i < board.length;i++){
           for(int j = 0; j < board[0].length;j++){
               //backtricking 
               backtricking(sb,ans,board,visited,i,j,wordLength);
               visited[i][j] = false;
               sb = new StringBuilder();
           }
       }
       //find the word from List<String> 
       for(String value: ans){
           if(value.equals(word))
            return true;
       }
       return false; 
    }
    
    public void backtricking(StringBuilder sb, List<String> ans, char[][] board,boolean[][] visited,int row,int col,int wordLength){
      // add elements  
      sb.append(board[row][col]); 
      visited[row][col] = true; 
      //recursion stop condition 
      if(sb.length() == wordLength){
          //collect string which length is equal to word.length
          ans.add(sb.toString());
          return; 
      }
      //for loop for this layer 
      for(int[] d : direction){
         //process the nodes according to the requirements 
         int i = d[0] + row;
         int j = d[1] + col;
        if(i >= 0 && i < board.length && j >= 0 && j < board[0].length && !visited[i][j]){
          //recursion 
          backtricking(sb,ans,board,visited,i,j,wordLength);
          //undo previous operation 
          visited[i][j] = false;
          sb.delete(sb.length() - 1, sb.length());
        }
      }  
    }
}

version 2

This is the optimized version.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
class Solution {
    private static final int[][] direction = {{0,1},{0,-1},{-1,0},{1,0}};
    public boolean exist(char[][] board, String word) {       
       if (word == null || word.length() == 0) {
         return true;
       }
       if (board == null || board.length == 0 || board[0].length == 0) {
         return false;
       }
       boolean[][] visited = new boolean[board.length][board[0].length];
       for(int i = 0; i < board.length;i++){
           for(int j = 0; j < board[0].length;j++){
               //backtricking 
            if(backtricking(0,i,j,visited,board,word))
              return true;
           }
       }
       return false; 
    }
    
    public boolean backtricking(int count, int row, int col, boolean[][] visited,char[][] board,String word){
      //recursion stop condition 
      if(count == word.length()) 
        return true;
      //recursion stop condition 
      if(row < 0 || row >= board.length || col < 0 || col >= board[0].length || board[row][col] != word.charAt(count) || visited[row][col]){
        return false; 
      } 
       
      
      //record passed nodes 
      visited[row][col] = true;
      //for loop for this layer 
      for(int[] d: direction){
        //process the nodes 
        int i = d[0] + row; 
        int j = d[1] + col;
        //recursion
        if(backtricking(count+1,i,j,visited,board,word))
          return true;   
      }
      
       //undo previous opperation 
       visited[row][col] = false;
       
       return false;
    }
}