题目

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

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

示例 1：

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

示例 2：

输入：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "SEE"
输出：true

示例 3：

输入：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCB"
输出：false

提示：

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

进阶： 你可以使用搜索剪枝的技术来优化解决方案，使其在 board 更大的情况下可以更快解决问题？

题解

public boolean exist(char[][] board, String word) {
    int rows, columns;
    if ((rows = board.length) == 0 || (columns = board[0].length) == 0) {
        return false;
    }
    // 记录是否已使用
    boolean[][] blackboard = new boolean[rows][columns];
    // 回溯搜索
    BiFunction<Integer, Integer, Boolean> backtrack = new BiFunction<Integer, Integer, Boolean>() {
        // 字符匹配索引
        private int index = 0;

        @Override
        public Boolean apply(Integer row, Integer column) {
            if (board[row][column] == word.charAt(index)) {
                // 匹配完成
                if (index + 1 == word.length()) {
                    return true;
                }
                // 向下遍历
                if (row - 1 >= 0 && !blackboard[row - 1][column]) {
                    blackboard[row][column] = true;
                    this.index++;
                    boolean flag = this.apply(row - 1, column);
                    blackboard[row][column] = false;
                    this.index--;
                    if (flag) {
                        return true;
                    }
                }
                // 向上遍历
                if (row + 1 < rows && !blackboard[row + 1][column]) {
                    blackboard[row][column] = true;
                    this.index++;
                    boolean flag = this.apply(row + 1, column);
                    blackboard[row][column] = false;
                    this.index--;
                    if (flag) {
                        return true;
                    }
                }
                // 向右遍历
                if (column - 1 >= 0 && !blackboard[row][column - 1]) {
                    blackboard[row][column] = true;
                    this.index++;
                    boolean flag = this.apply(row, column - 1);
                    blackboard[row][column] = false;
                    this.index--;
                    if (flag) {
                        return true;
                    }
                }
                // 向左遍历
                if (column + 1 < columns && !blackboard[row][column + 1]) {
                    blackboard[row][column] = true;
                    this.index++;
                    boolean flag = this.apply(row, column + 1);
                    blackboard[row][column] = false;
                    this.index--;

                    // 最后一种 可以直接返回
                    return flag;
                }
            }

            return false;
        }
    };

    // 从网格中每个字符开始回溯是否能匹配word
    for (int i = 0; i < rows; i++) {
        for (int j = 0; j < columns; j++) {
            if (backtrack.apply(i, j)) {
                return true;
            }
        }
    }

    return false;
}