关于javascript:LeetCode079单词搜索

43次阅读

共计 2088 个字符，预计需要花费 6 分钟才能阅读完成。

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

单词必须依照字母程序，通过相邻的单元格内的字母形成，其中“相邻”单元格是那些程度相邻或垂直相邻的单元格。同一个单元格内的字母不容许被重复使用。

示例阐明请见 LeetCode 官网。

起源：力扣（LeetCode）
链接：https://leetcode-cn.com/probl…
著作权归领扣网络所有。商业转载请分割官网受权，非商业转载请注明出处。

解法一：回溯算法

首先，直接判断 2 种非凡场景：

如果要匹配的字符串为空，间接返回 true；

如果 board 数组为空，间接返回 false。

否则，先申明一个和 board 同样大小的 boolean 类型的数组，记录以后单元格是否曾经走过，而后遍历 board 的每一个字符，对每一个字符和 word 第一个字符相等的时候，调用回溯办法进行判断以以后字符为终点是否可能匹配 word 字符串，如果能返回 true，否则持续遍历下一个字符。最初，如果没有匹配胜利，返回 false。

public class LeetCode_079 {public static boolean exist(char[][] board, String word) {
        /**
         * 如果要匹配的字符串为空，间接返回 true
         */
        if (word == null || word.length() == 0) {return true;}
        /**
         * 如果 board 数组为空，间接返回 false
         */
        if (board == null || board.length == 0 || board[0].length == 0) {return false;}
        /**
         * 申明一个和 board 同样大小的 boolean 类型的数组，记录以后单元格是否曾经走过
         */
        boolean[][] visited = new boolean[board.length][board[0].length];
        for (int i = 0; i < board.length; i++) {for (int j = 0; j < board[0].length; j++) {
                /**
                 * 对每一个字符和 word 第一个字符相等的时候，调用办法进行判断
                 */
                if (board[i][j] == word.charAt(0) && exist(board, visited, word, i, j, 0)) {return true;}
            }
        }
        return false;
    }

    /**
     * 回溯算法
     *
     * @param board   原字符网格
     * @param visited 和 board 大小雷同的 boolean 类型的网格，标识以后字符是否走过
     * @param word    要匹配的单词
     * @param startX  以后单元格的 x 坐标
     * @param startY  以后单元格的 y 坐标
     * @param pos     以后曾经匹配了几个字符
     * @return
     */
    private static boolean exist(char[][] board, boolean[][] visited, String word, int startX, int startY, int pos) {if (board[startX][startY] != word.charAt(pos)) {
            // 如果以后单元格和要匹配的字符不同，间接返回 false
            return false;
        } else if (pos == word.length() - 1) {
            // 如果曾经匹配的字符数和 word 的长度相等，则阐明曾经匹配胜利，返回 true
            return true;
        }

        visited[startX][startY] = true;
        // 以后单元格能够往四个方向挪动
        int[][] directions = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
        boolean result = false;
        for (int[] dir : directions) {int nextStartX = startX + dir[0], nextStartY = startY + dir[1];
            if (nextStartX >= 0 && nextStartX < board.length && nextStartY >= 0 && nextStartY < board[0].length) {if (!visited[nextStartX][nextStartY]) {boolean flag = exist(board, visited, word, nextStartX, nextStartY, pos + 1);
                    if (flag) {
                        result = true;
                        break;
                    }
                }
            }
        }
        visited[startX][startY] = false;
        return result;
    }

    public static void main(String[] args) {char[][] board = new char[][]{{'A', 'B', 'C', 'E'}, {'S', 'F', 'C', 'S'}, {'A', 'D', 'E', 'E'}};
        // 测试用例，冀望返回：true
        System.out.println(exist(board, "ABCCED"));
    }
}