【Leetcode 热题 100】79. 单词搜索

问题背景

给定一个 $m\times n$ 二维字符网格 $board$ 和一个字符串单词 $word$。如果 $word$ 存在于网格中，返回 $true$；否则，返回 $false$。
单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。

数据约束

• $m=board.length$
• $n=board[i].length$
• $1\le m,n\le 6$
• $1\le word.length\le 15$
• $board$ 和 $word$ 仅由大小写英文字母组成

解题过程

这题放在了回溯这个类别下，其实更适合当作图的深度优先遍历相关问题来解决，可以参考模板题 岛屿数量。
一般做法的框架是定义四个方向，对图中每个节点都尝试搜索它的相邻节点，在不越界且并且和字符串相应位置的字符相同时，进一步递归检查。
有两个可以优化的地方。
一是通过遍历搭配哈希表来统计图中和字符串中每种字符出现的次数，一旦发现字符串中所要求的某种字符出现的次数大于图中对应字符出现的次数，就不可能满足条件，可以避免深搜，直接返回结果。
这样做的时间消耗是 $O(N^2)$，要比暴力搜索的指数级好得多。
在此基础上，考虑到返回 $false$ 的情况是某个字符处不匹配造成的，并且遍历字符串的顺序对结果没有影响可以比较字符串中第一个字符和最后一个字符出现的次数，从要求比较高的那一头开始搜索，这样更容易出现不满足条件返回的情形，可以有效减少递归搜索的次数。

具体实现

class Solution {
    private static final int[][] DIRECTIONS = {{0, -1}, {0, 1}, {-1, 0}, {1, 0}};

    public boolean exist(char[][] board, String word) {
        // 统计图中每种字符出现的次数
        int[] count = new int[128];
        for(char[] row : board) {
            for(char c : row) {
                count[c]++;
            }
        }
        // 优化一，统计字符串中每种字符要求的次数，如果大于图中出现的相应字符数，直接返回 false
        char[] chW = word.toCharArray();
        int[] wordCount = new int[128];
        for(char c : chW) {
            if(++wordCount[c] > count[c]) {
                return false;
            }
        }
        // 优化二，颠倒单词顺序不影响结果，从出现次数多的那头开始搜索
        if(count[chW[chW.length - 1]] < count[chW[0]]) {
            chW = new StringBuilder(word).reverse().toString().toCharArray();
        }
        // 常规框架，对图中的每个字符位置都尝试进行搜索
        for(int i = 0; i < board.length; i++) {
            for(int j = 0; j < board[0].length; j++) {
                if(dfs(i, j, 0, board, chW)) {
                    return true;
                }
            }
        }
        return false;
    }

    private boolean dfs(int x, int y, int i, char[][] board, char[] word) {
        if(board[x][y] != word[i]) {
            return false;
        }
        // 注意，执行到这里的时候已经判断了图中当前字符和字符串对应位置的字符相同，到达了边界
        if(i == word.length - 1) {
            return true;
        }
        // 修改图，用来标记已访问过
        board[x][y] = 0;
        for(int[] direction : DIRECTIONS) {
            int nextX = x + direction[0];
            int nextY = y + direction[1];
            // 只有在不越界且进一步递归也返回 true 的情况下，当前位置才能返回 true
            if(0 <= nextX && nextX < board.length && 0 <= nextY && nextY < board[0].length && dfs(nextX, nextY, i + 1, board, word)) {
                return true;
            }
        }
        // 恢复现场
        board[x][y] = word[i];
        return false;
    }
}