一.题目介绍
1.题目来源
链接：LeetCode
2.题目
给定一个mxn二维字符网格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
二.具体实现
1.实现思路
针对查找一类的题目，遍历是肯定的，还有就是回溯算法的应用，我们得把字符串中所有的元素都进行判断，如果没有满足条件则会继续往下面遍历直到最后一个元素。
2.实现代码
1)自己的实现方式
public boolean exist(char[][] board, String word) { if (word == null || word.length() == 0 || board.length == 0 || board[0].length == 0) { return false; } int row = board.length, column = board[0].length; boolean[][] visited = new boolean[row][column]; for (int i = 0; i < row; i++) { for (int j = 0; j < column; j++) { // 找到其实位置（可能有多个） if (board[i][j] == word.charAt(0)) { if (backtrack(0, i, j, board, word, visited)) { return true; } } } } return false; } public boolean backtrack(int index, int i, int j, char[][] board, String word, boolean[][] visited) { int row = board.length; int column = board[0].length; // 超出二维网格，直接返回false if (i < 0 || j < 0 || i > row - 1 || j > column - 1) { return false; } // 重复使用，直接返回false if (visited[i][j]) { return false; } // 找到结果，返回true if (index == word.length() - 1) { return word.charAt(index) == board[i][j]; } // 回溯 if (word.charAt(index) == board[i][j]) { visited[i][j] = true; if (backtrack(index + 1, i + 1, j, board, word, visited) || backtrack(index + 1, i - 1, j, board, word, visited) || backtrack(index + 1, i, j + 1, board, word, visited) || backtrack(index + 1, i, j - 1, board, word, visited)) { return true; } visited[i][j] = false; } return false; } 复制代码
2)题友的实现方式
深度优先&回溯算法：
3.运行结果
三.题后思考
对于回溯算法大家都不陌生，为此还有题友写成了回溯算法的模板，只要按模板套题都能灵活解题，算是开辟了一种做题的方式吧，有的算法题还是很磨人的。
