アルゴリズム16 Word Search

タイトル:Given a 2 Dboard and a word,find if the word exists in the grid.
The word can be constructed from letters of sequentially adjacent cell, where "adjacent"cells are those horizontally or vertically neighboring. The same letter cell may not be used more than once.
For example, Given board =
[ ['A','B','C','E'], ['S','F','C','S'], ['A','D','E','E'] ] word = "ABCCED", -> returns true, word = "SEE", -> returns true, word = "ABCB", -> returns false. (この問題は英語でもっと正確に表現します)考え方:この問題を見たとき、行列の中で探して、単語の中で比べてみたいと思っていましたが、具体的にはどうすればいいか分かりませんでした.だから、他の人の良い考えを勉強しました.ここでは、具体的で明確な解法を簡単に説明します.タイトルを言い換えると、このboardでpathを歩くように、このwordのpathを見つけることができますか.ではpathを歩き、まず起点を見つけ、boardを巡り、wordの最初のアルファベットと同じように起点として私たちの再帰functionに代入します.各ポイントの位置を記録するので、列と行を記録します.私たちはwordの中のアルファベットを記録しなければならないので、wordIndexが必要です.最も重要なのは、私たちがすでに歩いた点を判断する必要があるので、boolean markBoardが必要です[][];起点(各点)に対して、最も基本的な考え方は、4つの方向を歩いて、その方向の次の点を再帰することができて、1本のpathが成功したら、帰ってきて直接returnすることができて、すべてのpathesを読み続ける必要はありません;各ポイントについて、1、wordがreturn trueを見つけたかどうかを確認します.また、2、この点が探索できるかどうかを確認します(例えば、この点はboardの範囲を超えており、wordのcharと等しくなく、探索されています)、return false.
複雑度時間O(N^2)空間O(N)
コード:

public boolean exist(char[][] board, String word) 
{
    if(board == null || board.length == 0 
            || board.length * board[0].length < word.length())
        return false;
    
    boolean[][] mark = new boolean[board.length][board[0].length];
    boolean res = false;
    //  board,    word         ，   path
    for(int i=0; i= board.length || row < 0 ||  col >= board[0].length || col < 0
            || word.charAt(wordIndex) != board[row][col] || markBoard[row][col])
        return false;
    
    
    //           
    markBoard[row][col] = true;
    
    //            
    //                 ，            
    if(findWord(board, word, wordIndex + 1, row - 1, col, markBoard) || // go top
       findWord(board, word, wordIndex + 1, row, col + 1, markBoard) || // go right
       findWord(board, word, wordIndex + 1, row + 1, col, markBoard) || // go bottom:
       findWord(board, word, wordIndex + 1, row, col - 1, markBoard))   // go left:
    {
        return true;
    }
    
    markBoard[row][col] = false; //          

    //             ，         
    return false;
}