What would you do if you were looking for a fixed string in a matrix?

The link refers to the path in the Offer 12 matrix

Same solution main site link: 79. Word search

First, look at the problem

Design a function that determines whether there is a path in a matrix that contains all the characters of a string. The path can start at any cell in the matrix, and each step can move one cell left, right, up, or down in the matrix. If a path passes through a cell of the matrix, the path cannot enter that cell again. For example, the path containing a string “bfCE” in the 3×4 matrix below (the letters in the path are indicated).

[[“a”,”b“,”c”,”e”],

[“s”,”f“,”c“,”s”],

[“a”,”d”,”e“,”e”]]

Example:

Input: board = [[” A “, “B”, “C”, “E”], [” S “, “F”, “C”, “S”], [” A “, “D”, “E”, “E”]], the word = “ABCCED”

Output: true,

Example 2:

Board = [[“a”,”b”],[“c”,”d”]], word = “abcd”

Output: false

Tip:


  • 1 < = b o a r d . l e n g t h < = 200 1 <= board.length <= 200

  • 1 < = b o a r d [ i ] . l e n g t h < = 200 1 <= board[i].length <= 200

Second, organize your thoughts

The title contains a lot of information and limitations, so let’s analyze it bit by bit to clarify our thoughts.

The first step:

Confirm input and output:

Input: a two-dimensional array; Output: Boolean value.

The second step

What do you do with the input to get the output?

In the explanation of the stem of the problem, it means to find an orderly path, and that path has similar conditions for each cell, but in addition, it cannot go through the same cell.

From these two points, it’s easy to think that this problem should be recursively processed. And you need some way to keep track of the status of the cells you’ve walked through.

Therefore, the following algorithm is obtained:

/ * * *@param {character[][]} board
 * @param {string} word
 * @return {boolean}* /
function find(board, wordArr, status, i, j, idx) {
    // Consider boundary cases as well as character contrast and repetition
    if (i < 0 || j < 0 || i > board.length - 1 || j > board[0].length - 1|| board[i][j] ! = wordArr[idx] || status[i][j] ==0) return false
    // The last character was found successfully
    if (idx == wordArr.length-1) return true
    status[i][j] = 0
    // look up, down, left, and right
    res = find(board, wordArr, status, i + 1, j, idx + 1) || find(board, wordArr, status, i, j + 1, idx + 1) || find(board, wordArr, status, i - 1, j, idx + 1) || find(board, wordArr, status, i, j - 1, idx + 1)
    // If no result is found, the character state will be restored
    status[i][j] = 1
    return res
}

var exist = function (board, word) {
    let status = []
    // It is worth noting that when the value filled in fill is a reference type,
    // Changing the value of one fill unit changes all the fill units.
    // Use the for loop instead
    for(let i=0; i<board.length; i++){ status.push(new Array(board[0].length).fill(1))}let wordArr = Array.from(word)
    for(let i=0; i<board.length; i++){for(let j=0; j<board[0].length; j++){if(find(board,wordArr,status,i,j,0)) return true}}return false
};
Copy the code

One of the hardest things to do on your own was to sort out the DFS thinking. The false case was obvious, but the condition to return true was not immediately in mind. Another point is the operation of state restoration. At first, I didn’t know how to deal with it. Later, after referring to the solution of the problem, I realized that no matter whether it returned true or false, we should restore it after the judgment, so that the judgment of the subordinate will not affect the superior.

Another way to reduce space complexity is posted below for your reference:

/ * * *@param {character[][]} board
 * @param {string} word
 * @return {boolean}* /
function find(board, wordArr, i, j, idx) {
    // Consider boundary cases as well as character contrast and repetition
    if (i < 0 || j < 0 || i > board.length - 1 || j > board[0].length - 1|| board[i][j] ! = wordArr[idx])return false
    // The last character was found successfully
    if (idx == wordArr.length-1) return true
    // Change the array to null
    board[i][j] = '\ 0'
    // look up, down, left, and right
    res = find(board, wordArr, i + 1, j, idx + 1) || find(board, wordArr, i, j + 1, idx + 1) || find(board, wordArr, i - 1, j, idx + 1) || find(board, wordArr, i, j - 1, idx + 1)
    // If no result is found, the character state will be restored
    // Restore the null character
    board[i][j] = wordArr[idx]
    return res
}

var exist = function (board, word) {
    let wordArr = Array.from(word)
    for(let i=0; i<board.length; i++){for(let j=0; j<board[0].length; j++){if(find(board,wordArr,i,j,0)) return true}}return false
};
Copy the code

This method reduces the space consumption of state variables by temporarily modifying the original array. But in real tests, frequent changes to the array’s characters actually increased memory consumption and were faster overall, probably because of the reduced time spent creating state variables.

Third, summary

Find a path

Solution: DFS+ pruning

When the topic is complex, we can analyze the conditions given in the topic again, find the boundary conditions, and then carry out algorithm analysis according to the appropriate ideas, simplify the complex topic and summarize it into the familiar system is the correct way to solve the problem.

Come on!

This article is participating in the “Nuggets 2021 Spring Recruitment Campaign”, click to see the details of the campaign