Nuggets team number online, help you Offer impromptu! Click on theCheck the details

1. Title Description

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 the string “bfCE” in the 3×4 matrix below (the letters in the path are highlighted in bold).

[["a","b","c","e"],
["s","f","c","s"],
["a","d","e","e"]]
Copy the code

But the matrix does not contain the path to the string “abfb” because the path cannot enter the matrix again after the first character B of the string occupies the first row and the second cell.

Example 1:

The input

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

The output

true
Copy the code

Example 2:

The input

board = [["a","b"],["c","d"]], word = "abcd"
Copy the code

The output

false
Copy the code

prompt

1 <= board.length <= 200
1 <= board[i].length <= 200
Copy the code

Second, train of thought analysis

My train of thought

  1. I didn’t figure it out, in fact, because I overthought it, and they didn’t describe it clearly, because most of the solutions are paths that are continuous, and they don’t say paths that are discontinuous
  2. The difficulty of the solution given by this question is much different from my understanding of the meaning of the question (the question only says inclusion, not sequence and continuity).

The best way of thinking

  • DFS + backtracking
  • We start by iterating through the two-dimensional array and enter depth-first traversal DFS when the first number matches the first character of a given word.
    • Depth traversal is a way up, down, left, or right. If the path has already been traveled and the boundary of the array, return false to indicate that the path has not been traveled. As long as it passes, you can recurse until all the words have been matched.
  • So if you have something like ABCD and you have a path in the result matrix ABCC, ABCD goes to B and you have two cs. So the one that went CC first will keep returning false, and when it gets to B, B will keep going down another path.

AC code

Best written:

public boolean exist(char[][] board, String word) {
    char[] words = word.toCharArray();
    // Traverse the array to match the first character
    for (int i = 0; i < board.length; i++) {
        for (int j = 0; j < board[i].length; j++) {
            if (dfs(board, words, i, j, 0)) {
                // Returns if DFS finds the path
                return true; }}}return false;
}
/** * compare word[k] with the elements in a two-dimensional array. If they are identical, proceed to the next element. If they are different, return false **@paramBoard two-dimensional array *@paramWord needs to find the path *@paramI The I value of the current position of the two-dimensional array *@paramJ The j value of the current position of the two-dimensional array *@paramK word has traversed to the position */
public boolean dfs(char[][] board, char[] word, int i, int j, int k) {
    / / if you touch the boundary | | current character and need characters do not match, this road impassability
    if (i >= board.length || i < 0 || j >= board[0].length || j < 0 ||
        return false;
    }
    // *** * core *** recursively pop-up condition, words last character match also found
    if (k == word.length - 1) {
        return true;
    }
    // Since the traversal node cannot go any further, set it to '\0', so that never matching means never going this way.
    // Note that the current iteration thought that the path worked, but finally found that the path did not work, and you need to change the number back on the return.
    board[i][j] = '\ 0';
    // **** Core of the core ****
    // This is the key of recursion. If the current character is found to match, recurse it in the direction of up, down, left, and right.
    if (dfs(board, word, i + 1, j, k + 1) | |/ / to the right
            dfs(board, word, i - 1, j, k + 1) | |/ / to do
            dfs(board, word, i, j + 1, k + 1) | |/ / down
            dfs(board, word, i, j - 1, k + 1)) { / / up
        return true;
    }
    // If you find that the most red is not through, change the value back
    board[i][j] = word[k];
    return false;
}
Copy the code

Four,

The premise is that the path is continuous. If it is not continuous, it will return false all the way to the broken point.