给定一个 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，避免无意义搜索。
第二个优化：优先搜索稀有字符
如果单词的第一个字符比最后一个字符在棋盘中出现次数更多，就把单词反转，从稀有字符开始搜索。
这样可以更快地发现不匹配，减少搜索次数。
稀有宝石难找，先找稀有的