一、题目
1、算法题目
“给定一个二维数组和一个单词，如果单词存在网格中返回true，否则返回false。”
题目链接：
来源：力扣（LeetCode）
链接：79. 单词搜索 - 力扣（LeetCode） (leetcode-cn.com)
2、题目描述
给定一个 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 复制代码
二、解题
1、思路分析
类似找出所有可能解的问题，首先就可以想到用回溯算法。
这道题意思是从网格(i,j)开始搜索，找到单词word[k...]，如果搜索到就返回true，不然就返回false。
理一下思路就是：
- 遍历搜索，网格(i,j)≠单词[k]，那么这个字符就是不匹配的，返回false
- 如果已经搜索到单词末尾，但是字符依旧是匹配的状态，返回true，否则返回false
- 通过当前位置，搜索所有相邻位置，然后根据相邻位置搜索所有子串，找到返回true，否则返回false
2、代码实现
代码参考：
class Solution { public boolean exist(char[][] board, String word) { int h = board.length, w = board[0].length; boolean[][] visited = new boolean[h][w]; for (int i = 0; i < h; i++) { for (int j = 0; j < w; j++) { boolean flag = check(board, visited, i, j, word, 0); if (flag) { return true; } } } return false; } public boolean check(char[][] board, boolean[][] visited, int i, int j, String s, int k) { if (board[i][j] != s.charAt(k)) { return false; } else if (k == s.length() - 1) { return true; } visited[i][j] = true; int[][] directions = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}}; boolean result = false; for (int[] dir : directions) { int newi = i + dir[0], newj = j + dir[1]; if (newi >= 0 && newi < board.length && newj >= 0 && newj < board[0].length) { if (!visited[newi][newj]) { boolean flag = check(board, visited, newi, newj, s, k + 1); if (flag) { result = true; break; } } } } visited[i][j] = false; return result; } } 复制代码
网络异常，图片无法展示
|
3、时间复杂度
时间复杂度 ： O(M N · 3L)
M，N是网格的长度和宽度，L是单词的长度。
空间复杂度： O(M N)
只需要使用一个临时数组O(MN)的空间即可。
三、总结
这道题使用了回溯算法去解题，其实对于这道题还有优化算法，那就是剪枝，遇到不匹配或已访问的字符时提前退出，可以提高算法的效率。
这也是深度优先搜索的思想，可以对使用过元素进行标记，标记完进入递归，在递归中进行字符匹配。
