单词搜寻
题目形容：给定一个 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")); }}【每日寄语】 顺境、是非降临，心中要持一“宽”字。