Sword finger offer 12 Path in matrix

Given a m x n Two dimensional character grid board And a string word word . If word Exists in the grid , return true ; otherwise , return false .

The words must be in alphabetical order , It's made up of letters in adjacent cells , among “ adjacent ” Cells are those adjacent horizontally or vertically . Letters in the same cell are not allowed to be reused .

for example , In the following 3×4 The matrix of contains the word “ABCCED”（ The letters in the word are marked ）.

Example 1：

Input ：board = [[“A”,“B”,“C”,“E”],[“S”,“F”,“C”,“S”],[“A”,“D”,“E”,“E”]], word = “ABCCED”
Output ：true
Example 2：

Input ：board = [[“a”,“b”],[“c”,“d”]], word = “abcd”
Output ：false

Tips ：

1 <= board.length <= 200
1 <= board[i].length <= 200
board and word It consists of upper and lower case English letters only

class Solution {
    
       public boolean exist(char[][] board, String word) {
    
        // Traversing a two-dimensional array takes each element as a header dfs

        char[] words = word.toCharArray();

        for(int i = 0; i < board.length; i++) {
    
            for(int j = 0; j < board[0].length; j++) {
    
                if(helper( i, j, board, words,0)) return true; // If there is a successful match, exit 
            }
        }
        return false;
    }




    //dfs Traverse 
    boolean helper(int i,int j,char[][] board,char[] word,Integer index) {
    


        // Termination conditions 
        if(i >= board.length || i < 0 || j >= board[0].length || j < 0||board[i][j] != word[index]){
    
                return false;
        } // Passed the above if It proves that the current element has been matched   All subsequent operations are matched with the previous operations 


        if ((index == word.length - 1)){
      // It matches and is the last element 
            return true;
        }


        else{
      // It matches but is not the last element 

            // operation 
            board[i][j] = '\0';


            // Recursively call 
            boolean res = helper(i+1,j,board,word,index+1)||helper(i-1,j,board,word,index+1)
                    ||helper(i,j+1,board,word,index+1)||helper(i,j-1,board,word,index+1);


            // Call... In four directions dfs

            // After the recursion, the empty element will be restored , Because the complete array is required to restart the call （ The main function needs to access each element in the array as a recursive header ,
            // Then you need a complete board）
            // Changing to blank only means that during this search , This element has been accessed , When initial i j When the change , Another search process started 
            board[i][j] = word[index];

            return res;  // Return the result of the call （ Is there a match in these four directions ）

        }
    }
}

Be careful ： To prevent access to elements that have already been accessed , You need to empty the accessed element .
But at the end of recursion, you need to set the element back to its original value , Because you may need to switch heads recursively