preface

The second semester of the third year, since the preparation work, will begin their own brush the journey. At present, I am looking at the topic in the offer. Have brushed nearly 30 questions, but now go to see a few days ago to make their own questions still can not be written out. So I think we should stop and review the previous problems, and sort out the routine of doing the problems. So brush their own ideas and thinking here to share with you.

Topic describes

Given a two-dimensional grid and a word, find out if the word exists in the grid.

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

Difficulty: Medium

Example:

Board = [[' A ', 'B', 'C', 'E'], [' S ', 'F', 'C', 'S'], [' A ', 'D', 'E', 'E']] for A given word = "ABCCED", return true for A given word = "SEE", Given word = "ABCB", return falseCopy the code

Tip:

Board and word contain only upper and lower case letters. 1 <= board.length <= 200 1 <= board[i].length <= 200 1 <= word.length <= 10^3Copy the code

Their thinking

  1. To find a word in a two-dimensional grid, you should first find the first letter of the word in the two-dimensional array. The two-dimensional array is then searched by depth first (DFS).

  2. The parameters of the DFS function should be the coordinates I, j, and the index to determine the number of words. In DFS you should first ensure that the values of I and j do not exceed the bounds of the two-dimensional array. Otherwise return false.

    if(i < 0 || i >= board.length || j >= board[0].length) return false;
Copy the code

  3. Board [I][j] = word[index] If so, word[index] is assigned to TMP, and board[I][j is assigned to 0 to indicate that the element has already been used. Then, it is tested to see if it matches the next letter in word. When all the searches have been done, the changes in the two-dimensional array should be undone, since a letter can only be used once.

    AC code

    /* * @lc app=leetcode.cn id=79 lang=javascript * * [79] Word search */

// @lc code=start
/ * * *@param {character[][]} board
 * @param {string} word
 * @return {boolean}* /
var exist = function (board, word) {
    for (let i = 0; i < board.length; i++) {
        for (let j = 0; j < board[0].length; j++) {
            // Look for the first matching character
            if (word[0] === board[i][j]) {
                if (dfs(i, j, 0)) {
                    return true; }}}}return false;

    function dfs(i, j, index) {
        if (i < 0 || i >= board.length || j >= board[0].length) return false;
        let flag = false;
        if (board[i][j] === word[index]) {
            if (index === word.length - 1) {
                return true;
            }
            let tmp = board[i][j];
            board[i][j] = '0';
            flag = flag || dfs(i + 1, j, index + 1);
            flag = flag || dfs(i - 1, j, index + 1);
            flag = flag || dfs(i, j + 1, index + 1);
            flag = flag || dfs(i, j - 1, index + 1);
            board[i][j] = tmp; 
        }
        returnflag; }};// @lc code=end
board = [
    ['A'.'B'.'C'.'E'],
    ['S'.'F'.'C'.'S'],
    ['A'.'D'.'E'.'E']]let word = "ABCCED";
Copy the code

    conclusion

    Backtracking algorithm is violence enumeration, is to try one by one. If you don’t meet the criteria half way through the list, prune in time and undo the previous choice. You need to recurse all the possible scenarios. Note also the conditions for ending the recursion. In this case, the first letter is not found after searching the two-dimensional array, I and j are less than the boundary of the two-dimensional array, and the value of index and the length of word string are the same.

This article is participating in the “Nuggets 2021 spring recruiting activity”, click to viewEvent details