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.

For example, the 3×4 matrix below contains the word “ABCCED” (the letters in the word are highlighted).

Answer key

This is a recursive problem about depth first search algorithm.

Every time a recursion problem is very headache, plus there is no systematic learning graph DFS algorithm. I started with the right idea, but I couldn’t write the code. It may be that the relevant code framework remembers unskilled relationships.

/** * @param {character[][]} board * @param {string} word * @return {boolean} */ var exist = function(board, word) { var cur = 0; var m = board.length; var n = board[0].length; Function DFS (I, j, k) {/ / I and j is the number of the coordinates of the if (I < 0 | | j < 0 | | I > = m | | j > = n | | board [I] [j]. == word[k]){ return false; } board[I][j] == word[k]; if(k === word.length - 1) return true; Var TMP = board[I][j]; Board [I][j] = "; // Lock it, since subsequent recursions are in 4 directions, There is no guarantee that one direction on the value of the / / up: I - 1, j / / down: the I + 1, j / / left: I, j - 1 / / right: I, j + 1 var isTrue = DFS (I - 1, j, k + 1) | | DFS (I + 1, j, k + 1) | | dfs(i,j-1,k+1) || dfs(i,j+1,k+1); board[i][j] = tmp; // return isTrue; } for(let i=0; i<m; i++){ for(let j=0; j<n; j++){ if(dfs(i,j,cur))return true; } } return false; };Copy the code

The board [I] [j]. == word[k] This if condition does a good job, effectively screening out more cases, (I didn’t think of myself). That locked place and restore site because, if the current position, unable to find out a right path, is to traverse the other points, but when traversing the other point, just the traversal of unsuccessful points may be now a on the traversal path must point, if not recovery, convenient cannot succeed.

Such as:

[[" C ", "A", "A"], [" A ", "A", "A"], [" B ", "C", "D"]] now want to find: "AAB"Copy the code

When we first walked through A at (1,0), we thought that this was the starting point of AAB, so we left it blank, and after doing the up, down, left, right judgment, we realized that this point didn’t look very good, but we didn’t restore it.

As A result, when we traverse to A at position (1,1), we start from A at position (1,1) to find A path, but since A at position (1,0) is empty, we will misjudge that this path is not feasible, but in fact it is feasible, as follows:

[[“C”,”A”,”A”], [“A”,“A”,”A”], [“B”,”C”,”D”]]

I just have to go through A at (1,0).

In fact, the real difficulty is not the idea, after all, I think DFS’s up, down, left and right judgment and double for loop is actually very violent, the real difficulty is the determination of boundary conditions, and the design of the whole code structure.