单词搜索

原题链接

使用的方法

深度优先搜索（DFS） + 回溯

解题思路

核心思想：从网格里的每个位置开始尝试匹配 word，每次只能往 上、下、左、右 走，并且同一个格子不能重复用。

• 首先，我们需要遍历整个网格，找到每个位置作为起点进行搜索。
• 对于每个起点，我们使用深度优先搜索（DFS）来尝试匹配 word。DFS 的基本思路是：从当前格子开始，检查它是否与 word 的当前字符匹配。如果匹配，我们继续向四个方向（上、下、左、右）进行搜索，尝试匹配 word 的下一个字符。
• 在搜索过程中，我们需要确保不越界，并且不能重复使用同一个格子。为了标记已经访问过的格子，我们可以暂时将其值修改为一个特殊字符（例如 #），以表示该格子已经被访问过。搜索完成后，我们需要将其恢复为原来的值，以便其他路径的搜索。
• 如果在某个路径上成功匹配了整个 word，我们就返回 true。如果所有路径都尝试过后仍然没有找到匹配的结果，我们就返回 false。

代码实现

class Solution {
    public boolean exist(char[][] board, String word) {
        int m = board.length;
        int n = board[0].length;

        for(int i=0; i<m; i++){
            for(int j=0; j<n; j++){
                if(dfs(board, word , i , j , 0))
                    return true;
            }
        }
        return false;
    }

    public boolean dfs(char[][] board,String word,int i,int j,int index){
        // 判断 word 是否全部判断完毕
        if(index == word.length()) return true;

        // 1.判断是否越界 2. 判断和当前字符是否匹配
        if(i < 0 || i >= board.length ||
            j < 0 || j >= board[0].length || 
            board[i][j] != word.charAt(index))
            return false;
        // 暂时标记当前格子已被访问
        char temp = board[i][j];
        board[i][j] = '#';

        // 上下左右继续搜索
        boolean found = dfs(board, word, i+1, j , index+1) || 
                        dfs(board, word, i-1, j , index+1) || 
                        dfs(board, word, i , j+1, index+1) ||
                        dfs(board, word, i , j-1, index+1);
        // 回溯
        board[i][j] = temp;

        return found;
    }
}