Topic describes

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:

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 ", "d"]], the word = "abcd" output: falseCopy the code

Tip:

  • 1 <= board.length <= 200
  • 1 <= board[i].length <= 200

solution

Depth-first search DFS solution.

Python3

class Solution: def exist(self, board: List[List[str]], word: str) -> bool: def dfs(i, j, cur): if cur == len(word): return True if i < 0 or i >= m or j < 0 or j >= n or visited[i][j] or word[cur] ! = board[i][j]: return False visited[i][j] = True next = cur + 1 res = dfs(i + 1, j, next) or dfs(i - 1, j, next) or dfs(i, j + 1, next) or dfs(i, j - 1, next) visited[i][j] = False return res m, n = len(board), len(board[0]) visited = [[False for _ in range(n)] for _ in range(m)] for i in range(m): for j in range(n): res = dfs(i, j, 0) if res: return True return FalseCopy the code

Java

class Solution {
    private boolean[][] visited;

    public boolean exist(char[][] board, String word) {
        int m = board.length, n = board[0].length;
        visited = new boolean[m][n];
        char[] chars = word.toCharArray();
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                boolean res = dfs(board, i, j, chars, 0);
                if (res) return true;
            }
        }
        return false;
    }

    private boolean dfs(char[][] board, int i, int j, char[] chars, int cur) {
        if (cur == chars.length) return true;
        if (i < 0 || i >= board.length || j < 0 || j >= board[0].length) return false;
        if (visited[i][j] || board[i][j] != chars[cur]) return false;
        visited[i][j] = true;
        int next = cur + 1;
        boolean res = dfs(board, i + 1, j, chars, next)
                || dfs(board, i - 1, j, chars, next)
                || dfs(board, i, j + 1, chars, next)
                || dfs(board, i, j - 1, chars, next);
        visited[i][j] = false;
        return res;
    }
}
Copy the code

JavaScript

/** * @param {character[][]} board * @param {string} word * @return {boolean} */ var exist = function (board, word) { let row = board.length; let col = board[0].length; let res = false; let isRead = [...new Array(row)].map(() => Array(col).fill(0)); for (let i = 0; i < row; i++) { for (let j = 0; j < col; j++) { if (res) break; if (board[i][j] === word[0]) { dfs(i, j, word); } } } function dfs(i, j, word) { if ( i < 0 || j < 0 || i >= row || j >= col || res || isRead[i][j] || board[i][j] ! == word[0] ) { return; } isRead[i][j] = 1; word = word.substring(1); if (word.length) { dfs(i - 1, j, word); dfs(i + 1, j, word); dfs(i, j - 1, word); dfs(i, j + 1, word); } else { res = true; return; } isRead[i][j] = 0; } return res; };Copy the code

C++

class Solution { public: bool dfs(vector<vector<char>>& board, string& word, int cur, int x, int y) { if (board[x][y] ! = word[cur]) { return false; } if (cur == word.size()-1) { return true; } char t = board[x][y]; board[x][y] = '*'; Int dx[4] = {-1, 0, 1, 0}; int dy[4] = {0, 1, 0, -1}; for (int k = 0; k < 4; DFS int a = x + dx[k], b = y + dy[k]; if (a >= 0 && a < board.size() && b >= 0 && b < board[0].size()) { if (dfs(board, word, cur+1, a, b)) { return true; } } } board[x][y] = t; return false; } bool exist(vector<vector<char>>& board, string word) { int x = board.size(); int y = board[0].size(); if (0 == x || 0 == y) { return false; } for (int i = 0; i < x; i++) { for (int j = 0; j < y; j++) { if (dfs(board, word, 0, i, j)) { return true; } } } return false; }};Copy the code