本质就是 深度优先搜索。

但是需要减枝操作(很重要)。

例题

题解

class Solution {
    public boolean exist(char[][] board, String word) {  
        char[] cword = word.toCharArray();
        for(int i = 0 ;i<board.length;i++){
            for(int j = 0;j<board[0].length;j++){
                 if(is_ok(i,j,0,board,cword)==true)
                    return true;
            }
        }
        return false;
    }

    boolean is_ok(int i,int j,int res,char[][] board,char[] cword){
        if(i<0||j<0||i>board.length-1||j>board[0].length-1 || board[i][j]!=cword[res])
            return false;
        if(res==cword.length - 1)
            return true;
        char temp = board[i][j];
        board[i][j] = '\0';
        res++;
        boolean qq = is_ok(i-1,j,res,board,cword) || is_ok(i,j-1,res,board,cword) || is_ok(i+1,j,res,board,cword) || is_ok(i,j+1,res,board,cword);
        board[i][j] = temp;
        return qq;
    }
}

有个很常规又很妙的减枝操作

  • 这里用visited数组的话,回溯时不好操作是否路过。
  • 所以我们可以通过节点时把点设置为空字符,最后操作完再变回去。