回溯法

 1 public class Solution {
 2 
 3     public static boolean exist(char[][] board, String word) {
 4         if(word.length() > board.length*board[0].length()) {
 5             return false;
 6         }
 7 
 8         boolean[][] boardFlag = new boolean[board.length][board[0].length];
 9         for(int i = 0; i < board.length; i++) {
10             for(int j = 0; j < board[0].length; j++) {
11                 if(find(i, j, board, word, boardFlag)) {
12                     return true;
13                 }
14             }
15         }
16 
17         return false;
18     }
19 
20     public static boolean find(int i, int j, char[][] board, String word, boolean[][] boardFlag) {
21         if(board[i][j] == word.charAt(0) && !boardFlag[i][j]) {
22 
23             boardFlag[i][j] = true;
24 
25             if(word.length-1 == 0) {
26                 return true;
27             }
28 
29             if(j + 1 < board[0].length) {
30                 if(find(i,j+1,board,word.substring(1,word.length()),boardFlag)) return true;
31             }
32 
33             if(j - 1 >= 0) {
34                 if(find(i,j-1,board,word.substring(1,word.length()),boardFlag)) return true;
35             }
36 
37             if (i+1 < board.length) {
38                 if(find(i+1,j,board,word.substring(1,word.length()),boardFlag)) return true;  
39             }
40                 
41             if (i-1 >= 0) {
42                 if(find(i-1,j,board,word.substring(1,word.length()),boardFlag)) return true;  
43             }
44 
45             // important here
46             boardFlag[i][j] = false;
47 
48             return false;
49         }
50     }
51 }