力扣79.单词搜索
原题，以下是题目描述：
题目会给一个字符类型的二维数组，一个字符序列，需要返回二维数组是否连续包含字符序列。
这题力扣难度评级是中等，我个人感觉也算中等（稍微偏下）。
思路
我们直接使用深度优先搜索，一个字符一个字符去搜索，然后按照左右上下的顺序去遍历，一旦碰到匹配成功的情况，直接结束递归，返回即可，当搜索完整个二维数组后都没搜索到，返回false。
代码一
我们看代码：
class Solution {
public boolean exist(char[][] board, String word) {
char c = word.charAt(0);
int l1 = board.length;
int l2 = board[0].length;
for (int i = 0; i < l1; i++) {
for (int j = 0; j < l2; j++) {
if (board[i][j] == c) {
if (exist2(board, word, new StringBuilder(), i, j, word.length())) {
return true;
}
board[i][j] = c;
}
}
}
return false;
}
public boolean exist2(char[][] board, String word, StringBuilder sb, int row, int col, int n) {
char t = board[row][col];
sb.append(t);
board[row][col] = 0;
if (n == 1) {
boolean flag = word.contentEquals(sb);
sb.deleteCharAt(sb.length() - 1);
return flag;
}
char c = word.charAt(word.length() - n + 1);
boolean f1 = false;
if (col + 1 < board[0].length && board[row][col + 1] == c) {
f1 = exist2(board, word, sb, row, col + 1, n - 1);
}
if (!f1 && col - 1 >= 0 && board[row][col - 1] == c) {
f1 = exist2(board, word, sb, row, col - 1, n - 1);
}
if (!f1 && row + 1 < board.length && board[row + 1][col] == c) {
f1 = exist2(board, word, sb, row + 1, col, n - 1);
}
if (!f1 && row - 1 >= 0 && board[row - 1][col] == c) {
f1 = exist2(board, word, sb, row - 1, col, n - 1);
}
sb.deleteCharAt(sb.length() - 1);
board[row][col] = t;
return f1;
}
}
这里稍微优化了一下：我们只在匹配对下一个的时候才转入下一次递归。这份代码提交打败百分之60左右。其实还可以继续优化。
代码二
我们这里其实是不需要那个StringBuilder的，我们每次只有匹配到序列后才会转入下一次递归，所以消耗完n后一定是正确序列。StringBuilder的添加和删除也是需要耗时的。我们去掉StringBuilder，得到如下代码：
class Solution {
public boolean exist(char[][] board, String word) {
char c = word.charAt(0);
int l1 = board.length;
int l2 = board[0].length;
for (int i = 0; i < l1; i++) {
for (int j = 0; j < l2; j++) {
if (board[i][j] == c) {
if (exist2(board, word, i, j, word.length())) {
return true;
}
}
}
}
return false;
}
public boolean exist2(char[][] board, String word, int row, int col, int n) {
char t = board[row][col];
if (t==0){
return false;
}
board[row][col] = 0;
if (n == 1) {
return true;
}
char c = word.charAt(word.length() - n + 1);
boolean f1 = false;
if (col + 1 < board[0].length && board[row][col + 1] == c) {
f1 = exist2(board, word, row, col + 1, n - 1);
}
if (!f1 && col - 1 >= 0 && board[row][col - 1] == c) {
f1 = exist2(board, word, row, col - 1, n - 1);
}
if (!f1 && row + 1 < board.length && board[row + 1][col] == c) {
f1 = exist2(board, word, row + 1, col, n - 1);
}
if (!f1 && row - 1 >= 0 && board[row - 1][col] == c) {
f1 = exist2(board, word, row - 1, col, n - 1);
}
board[row][col] = t;
return f1;
}
}
去掉了StringBuilder，提交时空打败百分之90。提升巨大。这里代码其实还有很多优化空间。详细，简单来说就是我们可以先统计board和word中的各个字符数，如果word中的某个字符大于board对应字符的数量，就直接返回false。第二点优化是看看word中第一个字符和最后一个字符的数量谁大，如果最后一个字符数量小于第一个字符数量，我们将word倒转匹配，这样可以提前跳过更多的不匹配项。引入这两个优化应该能打败百分百，感兴趣你可以自己试试。