分析

• 本题的考点：递归回溯。

• 首先我们枚举单词的起点，一共有$n \times m$个起点，然后从该起点开始暴搜，第一次最多有4个方向可以递归，之后最多有3个方向可以递归，因为不能往回搜。

• 确定起点后，对于该次暴搜，怎样保证我们不搜索之前已经搜索过的位置呢？我们可以将board中相应的位置变为一个特殊字符，比如.，表示已经被搜过了，之后回溯的时候再恢复即可。

代码

• C++

class Solution {
public:
    bool exist(vector<vector<char>>& board, string word) {

        for (int i = 0; i < board.size(); i++)
            for (int j = 0; j < board[0].size(); j++)
                if (dfs(board, word, 0, i, j)) 
                    return true;
        return false;
    }

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

    // 从board[x][y]开始搜索word[u]
    bool dfs(vector<vector<char>> &board, string& word, int u, int x, int y) {

        if (board[x][y] != word[u]) return false;
        if (u == word.size() - 1) return true;

        char t = board[x][y];
        board[x][y] = '.';
        for (int i = 0; i < 4; i++) {
            int a = x + dx[i], b = y + dy[i];
            if (a < 0 || a >= board.size() || b < 0 || b >= board[0].size() || board[a][b] == '.')
                continue;
            if (dfs(board, word, u + 1, a, b)) return true;
        }
        board[x][y] = t;
        return false;
    }
};

• Java

class Solution {

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

    public boolean exist(char[][] board, String word) {

        for (int i = 0; i < board.length; i++)
            for (int j = 0; j < board[0].length; j++)
                if (dfs(board, word.toCharArray(), 0, i, j))
                    return true;
        return false;
    }

    // 从board[x][y]开始搜索word[u]
    private boolean dfs(char[][] board, char[] word, int u, int x, int y) {

        if (board[x][y] != word[u]) return false;
        if (u == word.length - 1) return true;

        char t = board[x][y];
        board[x][y] = '.';
        for (int i = 0; i < 4; i++) {
            int a = x + dx[i], b = y + dy[i];
            if (a < 0 || a >= board.length || b < 0 || b >= board[0].length || board[a][b] == '.')
                continue;
            if (dfs(board, word, u + 1, a, b)) return true;
        }
        board[x][y] = t;
        return false;
    }
}

时空复杂度分析

• 时间复杂度：$O(n \times m \times 3 ^ k)$，n、m为行数、列数，k为word长度。

• 空间复杂度：$O(k)$。