今日分享 – 算法(十一) 搜索与回溯算法

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;
    }
}

复制