二维网格单词搜索递归算法性能优化求助

1. 复用StringBuilder和visited数组，消除频繁对象创建 #

原始代码每次递归都新建StringBuilder拷贝当前字符串，且每个起点都新建100x100的visited数组，内存开销和GC压力极大。改为复用对象+回溯重置：

• 每个起点仅创建一次StringBuilder和visited数组
• 递归时直接传递原对象，添加字符后在回溯阶段删除最后一个字符，同时将visited对应位置设为false

修改后核心片段：

// 起点调用处
StringBuilder currentWord = new StringBuilder();
boolean[][] visited = new boolean[n][n];
dfs(row, col, currentWord, visited, result, minimumWordLength);

// DFS方法内
private void dfs(...) {
  // 边界检查
  if (row < 0 || col < 0 || row >= n || col >= n || visited[row][col]) return;

  currentWord.append(board[row][col]);
  visited[row][col] = true;

  // 单词校验与结果添加逻辑...

  // 递归调用（直接传原对象）
  for (int[] dir : DIRS) {
    int newRow = row + dir[0];
    int newCol = col + dir[1];
    dfs(newRow, newCol, currentWord, visited, result, minimumWordLength);
  }

  // 回溯重置
  visited[row][col] = false;
  currentWord.deleteCharAt(currentWord.length() - 1);
}

2. 用Trie字典树替换词库查询，大幅提升校验效率 #

如果isValidPrefix和isValidWord是基于字符串匹配或HashSet查询，每次操作时间复杂度为O(k)或O(n)（k为字符串长度，n为词库大小）。改用Trie树：

• 提前将词库构建为Trie树，每个节点存储子节点映射和单词结束标记
• 递归时直接传递Trie节点，若当前字符无对应子节点则直接剪枝；若存在则继续递归，同时检查是否为单词结尾（满足长度要求则加入结果）

3. 调整前缀剪枝时机，减少无效递归 #

原始代码在添加当前字符前检查前缀，此时currentWord不包含当前字符，可能导致错误剪枝或无效递归。改为添加字符后立即检查：

currentWord.append(board[row][col]);
visited[row][col] = true;

// 前缀无效则直接回溯
if (currentWord.length() >= minimumWordLength && !isValidPrefix(currentWord.toString())) {
  visited[row][col] = false;
  currentWord.deleteCharAt(currentWord.length()-1);
  return;
}

4. 替换TreeSet为HashSet，降低结果插入开销 #

TreeSet插入和查询为O(logm)（m为结果数量），HashSet为O(1)。若不需要实时有序，先用HashSet收集结果，最后再转换为TreeSet或排序，比实时维护有序集合效率提升数倍。

5. 预定义方向数组，简化遍历逻辑 #

用预定义数组替代两层循环遍历8个方向，减少分支判断开销：

private static final int[][] DIRS = {{-1,-1}, {-1,0}, {-1,1}, {0,-1}, {0,1}, {1,-1}, {1,0}, {1,1}};

// 递归中遍历方向
for (int[] dir : DIRS) {
  int newRow = row + dir[0];
  int newCol = col + dir[1];
  if (newRow >=0 && newRow <n && newCol >=0 && newCol <n && !visited[newRow][newCol]) {
    dfs(newRow, newCol, currentWord, visited, result, minimumWordLength);
  }
}

6. 减少字符串转换次数 #

原始代码多次调用currentWord.toString()生成新字符串，开销极大。结合Trie优化后，可直接用StringBuilder的字符序列与Trie节点交互，无需频繁转换；若必须校验，缓存转换后的字符串避免重复生成。

内容的提问来源于stack exchange，提问作者user18688161