“This is the 8th day of my participation in the Gwen Challenge in November. Check out the details: The Last Gwen Challenge in 2021”

preface

The word search for question 79 is as follows:

Given an M x N two-dimensional character grid board and a string word. Return true if Word exists in the grid; Otherwise, return false.

Words must be formed in alphabetical order by letters in adjacent cells, where “adjacent” cells are those that are horizontally or vertically adjacent. Letters in the same cell are not allowed to be reused.

Example 1:

Input: board = [[" A ", "B", "C", "E"], [" S ", "F", "C", "S"], [" A ", "D", "E", "E"]], the word = "ABCCED" output: trueCopy the code

Example 2:

Input: board = [[" A ", "B", "C", "E"], [" S ", "F", "C", "S"], [" A ", "D", "E", "E"]], the word = "SEE" output: trueCopy the code

A, thinking

The passage contains two important information:

  • In the gridboardThe selected characters are all contiguous
  • The gridboardEach character can be selected only once

To solve the problem of selecting each character only once, we can use a two-dimensional array to store whether the character at that position has already been selected.

What about words made up of adjacent characters?

We can solve this problem by recursion. We define recursion as a function to find if the KTH element in the word (with four directions: up, down, left, and right) can be found starting with I and j in the grid.

Now that you have an idea, it is not difficult to realize it. The general steps are as follows:

  1. Traverse the gridboard
  2. judgeboard[i][j]Is equal to the first character in the word, if you don’t want to wait, continue traversing the grid. If it is equal, continue to judgei, jIs the starting point for whether the next character in the word can be found
  3. Return as soon as a set of results can be foundtrueCan be

For example

Here for example, the board = [[” A “, “B”, “C”, “E”], [” S “, “F”, “C”, “S”], [” A “, “D”, “E”, “E”]], the word = “SEE” as an example

  1. Traverse the gridboard
  2. wheni=1, j=0When, appearedboard[1][0] = word[0]. Therefore, continue toi=1, j=0As a starting point, the match cannot continue, so it terminates
  3. wheni=1, j=3When, appearedboard[1][3] = word[0]

    Continue toi=1, j=3As a starting point, can be foundboard[2][3] = word[1]

    And then toi=2, j=3As a starting point, can be foundboard[2][2] = word[2]
  4. Finally a correct set of results is found and returnstrueCan be

Second, the implementation

The implementation code

It is important to note that when a set of results is found, it should be stopped immediately without further search to prevent the correct results from being updated.

    int[][] selected;
    public boolean exist(char[][] board, String word) {
        selected = new int[board.length][board[0].length];  // Initialize the flag bit
        for (int i=0; i<board.length; i++) {
            for (int j=0; j<board[0].length; j++) {
                if (board[i][j] == word.charAt(0)) {
                    selected[i][j] = 1;
                    if (dfs(i, j, board, 1, word)) {
                        return true;
                    }
                    selected[i][j] = 0; }}}return false;
    }


    public boolean dfs(int i, int j, char[][] board, int k, String word){
        boolean flag = false;
        if (k == word.length())
            return true;
        if (i-1 > -1 && selected[i-1][j] == 0 && word.charAt(k) == board[i-1][j]) { / / up
            selected[i-1][j] = 1;
            flag = dfs(i-1, j, board, k+1, word);
            selected[i-1][j] = 0;
        }
        if(! flag && i+1 < board.length && selected[i+1][j] == 0 && word.charAt(k) == board[i+1][j]) {   / / down
            selected[i+1][j] = 1;
            flag = dfs(i+1, j, board, k+1, word);
            selected[i+1][j] = 0;
        }
        if(! flag && j-1 > -1 && selected[i][j-1] = =0 && word.charAt(k) == board[i][j-1]) {  / / to the left
            selected[i][j-1] = 1;
            flag = dfs(i, j-1, board, k+1, word);
            selected[i][j-1] = 0;
        }
        if(! flag && j+1 < board[0].length && selected[i][j+1] = =0 && word.charAt(k) == board[i][j+1]) {  / / to the left
            selected[i][j+1] = 1;
            flag = dfs(i, j+1, board, k+1, word);
            selected[i][j+1] = 0;
        }
        return flag;
    }
Copy the code

The test code

    public static void main(String[] args) {
        // board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "SEE"
        char[][] board = {{'A'.'B'.'C'.'E'}, {'S'.'F'.'C'.'S'}, {'A'.'D'.'E'.'E'}};
        char[][] board1 = {{'a'.'b'}};
        char[][] board2 = {{'C'.'A'.'A'}, {'A'.'A'.'A'}, {'B'.'C'.'D'}};
        boolean flag = new Number79().exist(board, "SEE");
        System.out.println(flag);
    }
Copy the code

The results of

Third, summary

Thank you to see the end, very honored to help you ~♥

If you think my writing is good, you might as well give me a thumbs-up! If you have any questions, please see the comments section