Leetcode 深度优先搜索 (1)

79. 单词搜索

给定一个 $m\times n$ 二维字符网格 $board$ 和一个字符串单词 $word$ 。如果 $word$存在于网格中，返回 $true$ ；否则，返回 $false$ 。

单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。

示例 1：

输入： board = [[“A”,“B”,“C”,“E”],[“S”,“F”,“C”,“S”],[“A”,“D”,“E”,“E”]], word = “ABCCED”
输出： true

问题分析

这个问题的核心要求：

• 在二维字符网格中寻找指定单词
• 单词必须由相邻单元格的字母按顺序构成
• 相邻指水平或垂直相邻（不包括对角线）
• 同一单元格在一次搜索中不能重复使用

算法框架

• 使用 DFS + 回溯 的经典模式：
• 遍历网格每个位置作为起点
• 从起点开始DFS搜索单词
• 使用回溯保证状态正确恢复

代码实现

class Solution {
    private char[][] board;
    private String word;
    private int m, n;
    // 四个方向：上、右、下、左
    private int[][] directions = {{-1,0}, {0,1}, {1,0}, {0,-1}};
    
    public boolean exist(char[][] board, String word) {
        if (board == null || board.length == 0 || word == null || word.length() == 0) {
            return false;
        }
        
        this.board = board;
        this.word = word;
        this.m = board.length;
        this.n = board[0].length;
        
        // 遍历每个位置作为起点
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (dfs(i, j, 0)) {
                    return true;
                }
            }
        }
        
        return false;
    }
    
    /**
     * DFS搜索
     * @param i 当前行
     * @param j 当前列
     * @param index 当前匹配到word的第几个字符
     * @return 是否能找到完整单词
     */
    private boolean dfs(int i, int j, int index) {
        // 边界检查
        if (i < 0 || i >= m || j < 0 || j >= n) {
            return false;
        }
        
        // 字符不匹配
        if (board[i][j] != word.charAt(index)) {
            return false;
        }
        
        // 找到完整单词
        if (index == word.length() - 1) {
            return true;
        }
        
        // 标记当前位置已访问
        char temp = board[i][j];
        board[i][j] = '#'; // 使用特殊字符标记
        
        // 向四个方向搜索
        boolean found = false;
        for (int[] dir : directions) {
            int newI = i + dir[0];
            int newJ = j + dir[1];
            
            if (dfs(newI, newJ, index + 1)) {
                found = true;
                break;
            }
        }
        
        // 回溯：恢复当前位置
        board[i][j] = temp;
        
        return found;
    }
}

算法优化之反向搜索

基本思想

反向搜索优化的核心思想是减少搜索起点的数量。在单词搜索问题中，我们需要遍历网格中的每个位置作为潜在的起点。但实际上，只有与目标单词首字符匹配的位置才可能成为有效起点。

优化策略
传统方法是固定从单词的第一个字符开始搜索，但我们可以选择从单词的最后一个字符开始，反向搜索整个单词。关键是要选择在网格中出现频率更低的字符作为起点。

为什么有效？
假设我们要在网格中搜索单词"HELLO"：

• 统计字符频率：
• 字符’H’在网格中出现了20次
• 字符’O’在网格中出现了5次

传统方法：

• 必须尝试20个’H’位置作为起点
• 对每个起点进行深度优先搜索

优化方法：

• 将单词反转为"OLLEH"
• 只需尝试5个’O’位置作为起点
• 搜索逻辑完全相同，只是方向相反

数学原理
时间复杂度从$O(m\times n\times 4^L)优化为O(k\times 4^L)$，其中：

• $m\times n$ 是网格总大小
• $k$ 是优化后的起点数量
• $L$ 是单词长度
• $4^L$ 表示每个起点的搜索分支数
• 当$k$远小于$m\times n$时，性能提升非常明显。

适用条件
这种优化在以下情况下效果最佳：

• 字符分布不均匀：某些字符在网格中出现频率明显不同
• 较长的单词：单词越长，减少起点数量的收益越大
• 大规模网格：网格越大，字符频率差异的影响越明显

局限性

• 首尾字符相同：如果单词首尾字符相同，无法通过反向搜索减少起点
• 字符分布均匀：如果所有字符出现频率相近，优化效果有限
• 额外开销：需要额外的字符统计和字符串反转操作

核心价值
这种优化的价值在于它是一种预处理优化，通过简单的字符频率分析就能显著减少搜索空间，而不需要改变核心的搜索算法逻辑。它体现了启发式优化的思想：通过观察数据特征来指导搜索策略，从而提升算法效率。

总的来说，反向搜索优化是一种巧妙的策略，它利用了字符分布的不均匀性来减少无效的搜索尝试，在保持算法正确性的同时显著提升了性能。

优化后的代码实现

class Solution {

    private char[][] board;
    private String word;
    private int m, n;
    private int[][] directions = {{-1,0}, {0,1}, {1,0}, {0,-1}};
    
    public boolean exist(char[][] board, String word) {
        if (board == null || board.length == 0 || word == null || word.length() == 0) {
            return false;
        }
        
        this.board = board;
        this.m = board.length;
        this.n = board[0].length;
        
        // 优化1：字符频率检查
        if (!hasEnoughChars(word)) {
            return false;
        }
        
        // 优化2：选择更好的搜索方向
        this.word = optimizeSearchDirection(word);
        
        // 遍历每个位置作为起点
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (board[i][j] == this.word.charAt(0) && dfs(i, j, 0)) {
                    return true;
                }
            }
        }
        
        return false;
    }
    
    private boolean hasEnoughChars(String word) {
        int[] boardCount = new int[128];
        for (char[] row : board) {
            for (char c : row) {
                boardCount[c]++;
            }
        }
        
        int[] wordCount = new int[128];
        for (char c : word.toCharArray()) {
            wordCount[c]++;
        }
        
        for (int i = 0; i < 128; i++) {
            if (wordCount[i] > boardCount[i]) {
                return false;
            }
        }
        return true;
    }
    
    private String optimizeSearchDirection(String word) {
        char first = word.charAt(0);
        char last = word.charAt(word.length() - 1);
        
        int firstCount = 0, lastCount = 0;
        for (char[] row : board) {
            for (char c : row) {
                if (c == first) firstCount++;
                if (c == last) lastCount++;
            }
        }
        
        return firstCount > lastCount ? 
            new StringBuilder(word).reverse().toString() : word;
    }
    
    private boolean dfs(int i, int j, int index) {
        // 找到完整单词
        if (index == word.length() - 1) {
            return true;
        }
        
        // 标记访问
        char temp = board[i][j];
        board[i][j] = '#';
        
        // 四方向搜索
        for (int[] dir : directions) {
            int newI = i + dir[0];
            int newJ = j + dir[1];
            
            if (isValid(newI, newJ) && 
                board[newI][newJ] == word.charAt(index + 1) &&
                dfs(newI, newJ, index + 1)) {
                
                board[i][j] = temp; // 提前恢复
                return true;
            }
        }
        
        // 回溯
        board[i][j] = temp;
        return false;
    }
    
    private boolean isValid(int i, int j) {
        return i >= 0 && i < m && j >= 0 && j < n;
    }
}

运行效果