【Leetcode】79. Word search

  Topic link ： Word search

Title Description ：

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 .

Topic analysis ： Determine whether words exist in the grid , The letters of words are required to be adjacent and continuous in the grid .

You need to compare each character in the grid with each character in the word ：

When a character meets the condition , Compare the next character in the word with the next character in the grid ;

When a character does not meet the condition , Just go back to the previous step , Update selection . using to flash back Method .

Ideas ：

1） The first letter of a word may appear anywhere on the grid , So you need to traverse the grid as a whole , Until you find the right word .

2） Because the adjacent four cells of the cell will repeat traversal , Lead to misjudgment of word elements , You need a two-dimensional array as a tag , Accessed cells can no longer be accessed .

3） Use another function check(i,j,k), Said to board[i][j] As a starting point , Can I find and in the grid word China and Israel word[k] Start with the same sequence of suffix strings . So, of course, the traversal is check(i,j,0).

Of course, since this topic uses search , You can also use dfs.

js The code is as follows ：

//  to flash back 
 var exist = function(board, word) {
    const h=board.length;
    const w=board[0].length;

    //  Tag array initialization 
    const visited=new Array(h);
    for(let i=0;i<h;i++){
        visited[i]=new Array(w).fill(false);
    }
    //  Direction array 
    const directions=[[0,1],[0,-1],[1,0],[-1,0]];
    //  Traversing a two-dimensional array ,check
    for(let i=0;i<h;i++){
        for(let j=0;j<w;j++){
            let ans=check(i,j,0);
            if(ans)
                return true;
        }
    }
    return false;
    //  From board[i][j] Can we find and word[index...] from index Start , The same sequence 
    function check(i,j,index){
        //  If the characters are different , be false
        if(board[i][j]!=word.charAt(index))
            return false;
        //  If the characters are the same , And last , Directly obtained true
        else if(index===word.length-1)
            return true;
        //  The description is not the last character , You also need to continue to judge the adjacent characters around it 
        //  Indicates that the point has been visited , It can no longer be used 
        visited[i][j]=true;
        let result=false;
        //  Traverse points in four directions , One is available 
        for(const [dx,dy] of directions){
            let newi=i+dx;
            let newj=j+dy;
            if(newi>=0 && newi<h && newj>=0 && newj<w){
                if(!visited[newi][newj]){
                    let temp=check(newi,newj,index+1);
                    if(temp){
                        result=true;
                        break;
                    }
                }
            }
        }
        //  Unmark 
        visited[i][j]=false;
        return result;
    }
};