79. 单词搜索:题解
给定一个 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
初始版本(时间超越23%)
解题思路
回溯法: 每次递归尝试四个方向的相邻格子,若匹配则继续递归查找。
标记访问: 使用特殊字符 #
标记已访问的格子,防止重复使用。
终止条件: 若找到完整的单词,直接返回。
class Solution {
public int[][] offset = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
public boolean exist(char[][] board, String word) {
List<String> res = new ArrayList<>();
int nx = board.length;
int ny = board[0].length;
for (int i = 0; i < nx; i++) {
for (int j = 0; j < ny; j++) {
if (res.size() != 0) {
return true;
}
if (board[i][j] == word.charAt(0)) {
char tmp = board[i][j];
StringBuilder bgin = new StringBuilder();
bgin.append(word.charAt(0));
board[i][j] = '#';
backTrace(board, word, bgin, res, i, j);
board[i][j] = tmp;
}
}
}
return res.size() != 0;
}
public void backTrace(char[][] board, String word, StringBuilder output, List<String> res, int x, int y) {
if (output.length() == word.length()) {
res.add(output.toString());
return;
}
int nx = board.length;
int ny = board[0].length;
for (int i = 0; i < 4; i++) {
int newX = x + offset[i][0];
int newY = y + offset[i][1];
if (newX < 0 || newX >= nx || newY < 0 || newY >= ny) {
continue;
}
char temp = word.charAt(output.length());
if (board[newX][newY] == temp) {
char tmp = board[newX][newY];
output.append(temp);
board[newX][newY] = '#';
backTrace(board, word, output, res, newX, newY);
output.deleteCharAt(output.length() - 1);
board[newX][newY] = tmp;
}
}
}
}
存在问题:
- 性能瓶颈: 使用
StringBuilder
和List
存储路径,耗费额外空间。 - 未进行预剪枝: 没有在遍历前判断字母频次,导致不必要的递归。
- 过度递归: 没有及时返回,导致回溯路径冗长
优化解法(时间超越100)--思路来自leetcode题解区(灵茶山艾府)
class Solution {
private static final int[][] DIRS = {{0, -1}, {0, 1}, {-1, 0}, {1, 0}};
public boolean exist(char[][] board, String word) {
int[] cnt = new int[128];
for (char[] row : board) {
for (char c : row) {
cnt[c]++;
}
}
// 优化一:字符频次预剪枝
char[] w = word.toCharArray();
int[] wordCnt = new int[128];
for (char c : w) {
if (++wordCnt[c] > cnt[c]) {
return false;
}
}
// 优化二:字符顺序优化
if (cnt[w[w.length - 1]] < cnt[w[0]]) {
w = new StringBuilder(word).reverse().toString().toCharArray();
}
for (int i = 0; i < board.length; i++) {
for (int j = 0; j < board[i].length; j++) {
if (dfs(i, j, 0, board, w)) {
return true;
}
}
}
return false;
}
private boolean dfs(int i, int j, int k, char[][] board, char[] word) {
if (board[i][j] != word[k]) return false;
if (k == word.length - 1) return true;
board[i][j] = 0; // 标记访问
for (int[] d : DIRS) {
int x = i + d[0];
int y = j + d[1];
if (0 <= x && x < board.length && 0 <= y && y < board[x].length && dfs(x, y, k + 1, board, word)) {
return true;
}
}
board[i][j] = word[k]; // 恢复状态
return false;
}
}
第一个优化:字符频次预检查
先统计棋盘中每个字符的数量,再统计单词中每个字符的数量。
如果单词中的某个字符次数多于棋盘中该字符次数,直接返回 false
,避免无意义搜索。
第二个优化:优先搜索稀有字符
如果单词的第一个字符比最后一个字符在棋盘中出现次数更多,就把单词反转,从稀有字符开始搜索。
这样可以更快地发现不匹配,减少搜索次数。
稀有宝石难找,先找稀有的