题目

Given a 2D board and a word, find if the word exists in the grid.

The word can be constructed from letters of sequentially adjacent cell, where "adjacent" cells are those horizontally or vertically neighboring. The same letter cell may not be used more than once.

Example:

board =
[
  ['A','B','C','E'],
  ['S','F','C','S'],
  ['A','D','E','E']
]

Given word = "ABCCED", return true.
Given word = "SEE", return true.
Given word = "ABCB", return false.

解法思路（一）

• 从 board 的第一个格子 (i, j) 开始，和 word 的第一个字母 word.charAt(index) 比较，如果这俩相等，在 (i, j) 的上右下左找 word.charAt(index + 1)；
  • 如果一直可以找着，会到 word 的最后一个字母和 board 的某个格子相等，在 board 就能找着 word；
  • 如果都没找着，(i, j) 这就走不通，从 (i, j + 1) 开始，和 word 的第一个字母 word.charAt(index) 比较；
• 如果 (i, j) 和 word.charAt(index) 一开始就不能，那么从 (i, j + 1) 开始和 word.charAt(index) 比较；

解法实现（一）

关键字

二维数组中的每一格都要走一遍递归 递归

实现细节

• 如果 (x, y) 的上右下左都不行，那么 (x, y) 这条路就走不通了，之前对 (x, y) 行的假定就要推翻，这就是递归到底了，撞到南墙了，回头了，然后心里默默的记着这条路走不通，这就是回溯回来要对之前的假定做个结论，行或是不行；

package leetcode._79;

public class Solution79_2 {

    private boolean[][] accepted;

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

        if (board != null) {
            accepted = new boolean[board.length][board[0].length];
        }

        boolean isOk = false;
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[i].length; j++) {
                isOk = match(board, word, 0, i, j);
                if (isOk) {
                    return true;
                }
            }
        }

        return false;
    }

    private boolean match(char[][] board, String word, int index, int x, int y) {

        if (index == word.length() - 1) {
            boolean existed = word.charAt(index) == board[x][y];
            accepted[x][y] = existed;
            return existed;
        }

        boolean isOk = false;
        if (word.charAt(index) == board[x][y]) {
            accepted[x][y] = true;
            if (isOk == false
                    && x - 1 >= 0
                    && accepted[x - 1][y] == false) {
                isOk = match(board, word, index + 1, x - 1, y);
            }
            if (isOk == false
                    && y + 1 < board[0].length
                    && accepted[x][y + 1] == false) {
                isOk = match(board, word, index + 1, x, y + 1);
            }
            if (isOk == false
                    && x + 1 < board.length
                    && accepted[x + 1][y] == false) {
                isOk = match(board, word, index + 1, x + 1, y);
            }
            if (isOk == false 
                    && y - 1 >= 0
                    && accepted[x][y - 1] == false) {
                isOk = match(board, word, index + 1, x, y - 1);
            }
        }

        if (isOk == false) {
            accepted[x][y] = false;
        }
        return isOk;
    }

}

返回 LeetCode [Java] 目录