“给定一个二维数组和一个单词,如果单词存在网格中返回true,否则返回false。”
题目链接:
来源:力扣(LeetCode)
链接:79. 单词搜索 - 力扣(LeetCode) (leetcode-cn.com)
给定一个 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
类似找出所有可能解的问题,首先就可以想到用回溯算法。
这道题意思是从网格(i,j)开始搜索,找到单词word[k...],如果搜索到就返回true,不然就返回false。
理一下思路就是:
代码参考:
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;
}
}
时间复杂度 : O(M N · 3L)
M,N是网格的长度和宽度,L是单词的长度。
空间复杂度: O(M N)
只需要使用一个临时数组O(MN)的空间即可。
这道题使用了回溯算法去解题,其实对于这道题还有优化算法,那就是剪枝,遇到不匹配或已访问的字符时提前退出,可以提高算法的效率。
这也是深度优先搜索的思想,可以对使用过元素进行标记,标记完进入递归,在递归中进行字符匹配。