算法

(DFS) $O(nm*3^{word.length})$

遍历board每个点，看它是否和word开头字母相同，如果相同就就进入dfs过程

dfs(board, word,now, x, y)

board是字母板，word是单词，now是已经匹配了word的位置，x，y是最后一次匹配成功的字母板的位置下标

在dfs过程中 上下左右四个方向去找能匹配word里下个字符的位置

dfs(board,word,now,x,y)
//匹配成功
if now==word.length-1
    return True
for nextPost in nextPostSet  //在下一步的可行集合里 枚举下一步要走哪
    if nextPost 符合条件
        标记nextPost已经走过了
        tmp=dfs(board,word,now+1,nextPost.x,nextPost.y)
        回溯，标记nextPost没走过
        如果匹配成功,则tmp为True，直接返回True
所有下一步可行的方案都没匹配成功，返回匹配失败False

注意： 一定要标记走过的点，避免重复使用 dfs递归回溯时，还要把不去走的点标记为可用

C++ 代码

class Solution {
public:
    int calc(int x, int y, int n, int m) {
        return x * m + y;
    }
    bool dfs(vector<vector<char>> &board, string &word, int now, int x, int y, int n, int m, map<int, bool> &visited) {

        int zx[10] = {0, 0, 1, -1};
        int zy[10] = {1, -1, 0, 0};

        //搜索成功
        if(now == word.size() - 1) {
            return true;
        }
        //枚举下次该往哪个方向走
        for(int k = 0; k < 4; k++) {
            int nx = x + zx[k];
            int ny = y + zy[k];
            // 判断非法条件
            if(nx < 0 || nx >= n || ny < 0 || ny >= m || board[nx][ny] != word[now + 1] || visited[calc(nx, ny, n, m)] == true) {
                continue;
            }
            //标记已经走过
            visited[calc(nx, ny, n, m)] = true;
            bool tmp = dfs(board, word, now + 1, nx, ny, n, m, visited);
            //回溯
            visited[calc(nx, ny, n, m)] = false;
            if(tmp) {
                return true;
            }
        }
        return false;
    }

    bool exist(vector<vector<char>> &board, string &word) {
        int n, m;
        n = board.size();
        m = board[0].size();

        //标识这个点是否走过
        map<int, bool>visited;
        // 枚举起点
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < m; j++) {
                if(word[0] == board[i][j]) {
                    visited[calc(i, j, n, m)] = true;
                    int tmp = dfs(board, word, 0, i, j, n, m, visited);
                    visited[calc(i, j, n, m)] = false;
                    if(tmp) {
                        return true;
                    }
                }
            }
        }
        return false;
    }
};

Java 代码

class Solution {
    int[] dx = {0, 0, -1, 1};
    int[] dy = {-1, 1, 0, 0};

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

    private boolean dfs(char[][] board, int x, int y, String word, int idx) {
        if (idx == word.length() - 1) return board[x][y] == word.charAt(idx);
        char c = board[x][y];
        if (c != word.charAt(idx)) return false;
        int n = board.length;
        int m = board[0].length;
        board[x][y] = '#';
        for (int i = 0; i < dx.length; ++i) {
                int nx = x + dx[i];
                int ny = y + dy[i];
                if (nx >= 0 && nx < n && ny >= 0 && ny < m && board[nx][ny] != '#') {
                    if (dfs(board, nx, ny, word, idx + 1)) return true;
                }
        }
        board[x][y] = c;
        return false;
    }
}

Python 代码

class Solution:
    def exist(self, board: List[List[str]], word: str) -> bool:
        def dfs(x, y, p):
            if p == l:
                return True
            for dirx, diry in [(0, 1), (0, -1), [-1, 0], (1, 0)]:
                curx, cury = x + dirx, y + diry
                if 0 <= curx < m and 0 <= cury < n and flag[curx][cury] and board[curx][cury] == word[p]:
                    flag[curx][cury] = False
                    if dfs(curx, cury, p + 1):
                        flag[curx][cury] = True
                        return True
                    flag[curx][cury] = True
            return False


        m, n = len(board), len(board[0])
        l = len(word)
        flag = [[True] * n for _ in range(m)]
        for i in range(m):
            for j in range(n):
                if board[i][j] == word[0]:
                    flag[i][j] = False
                    if dfs(i, j, 1):
                        return True
                    flag[i][j] = True
        return False