算法二刷复盘：LeetCode 79 单词搜索 131 分割回文串（Java 回溯精讲）

目录

一、LeetCode 79 单词搜索（中等）

题目描述

核心思路：DFS + 回溯 + 标记访问

Java 完整实现

复杂度分析

二、LeetCode 131 分割回文串（中等）

题目描述

核心思路：回溯 + 回文判断

Java 完整实现

复杂度分析

三、两道题的回溯模板对比

四、二刷感悟：回溯题的 “两大核心”

今天复盘两道经典回溯题，它们都是DFS + 回溯剪枝的典型代表，分别是二维矩阵的路径搜索问题和字符串的分割问题，掌握它们能帮你彻底吃透回溯题的核心模板和剪枝技巧。

一、LeetCode 79 单词搜索（中等）

题目描述

给定一个m x n二维字符网格board和一个字符串单词word。如果word存在于网格中，返回true；否则，返回false。单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中 “相邻” 单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。

核心思路：DFS + 回溯 + 标记访问

这道题的核心是在二维矩阵中进行深度优先搜索，需要注意：

1. 遍历所有起点：以矩阵中每个单元格为起点，尝试匹配单词的第一个字符。
2. 标记访问：为了避免重复访问同一个单元格，访问时将当前单元格标记为特殊字符（如#），回溯时恢复。
3. 方向搜索：每次搜索四个方向（上下左右），只要有一个方向能匹配后续字符，就继续递归。
4. 剪枝优化：如果当前字符与单词目标字符不匹配，直接返回。

Java 完整实现

java

运行

class Solution { public boolean exist(char[][] board, String word) { int m = board.length; int n = board[0].length; for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { // 以每个单元格为起点开始搜索 if (dfs(board, word, i, j, 0)) { return true; } } } return false; } /** * DFS 回溯搜索 * @param board 二维字符网格 * @param word 目标单词 * @param i 当前行 * @param j 当前列 * @param index 当前匹配到的单词索引 * @return 是否存在路径 */ private boolean dfs(char[][] board, String word, int i, int j, int index) { // 终止条件：匹配到单词末尾 if (index == word.length()) { return true; } // 边界判断或字符不匹配 if (i < 0 || i >= board.length || j < 0 || j >= board[0].length || board[i][j] != word.charAt(index)) { return false; } // 标记当前单元格为已访问 char temp = board[i][j]; board[i][j] = '#'; // 上下左右四个方向搜索 boolean found = dfs(board, word, i + 1, j, index + 1) || dfs(board, word, i - 1, j, index + 1) || dfs(board, word, i, j + 1, index + 1) || dfs(board, word, i, j - 1, index + 1); // 回溯：恢复单元格字符 board[i][j] = temp; return found; } }

复杂度分析

• 时间复杂度：O (m×n×3ᴸ)，其中 m、n 为矩阵行列数，L 为单词长度。每个单元格最多有 3 个后续方向可走（避免回头）。
• 空间复杂度：O (L)，递归栈深度为单词长度 L。

二、LeetCode 131 分割回文串（中等）

题目描述

给你一个字符串s，请你将s分割成一些子串，使每个子串都是回文串。返回s所有可能的分割方案。

核心思路：回溯 + 回文判断

这道题是字符串分割问题，核心是枚举所有可能的分割点，并判断分割出的子串是否为回文串：

1. 枚举分割点：从字符串的startIndex位置开始，尝试分割[startIndex, i]区间的子串。
2. 回文判断：判断当前分割的子串是否为回文串，如果是则加入路径，继续递归处理剩余部分。
3. 回溯恢复：递归结束后，将当前子串从路径中移除，尝试其他分割方式。

Java 完整实现

java

运行

import java.util.ArrayList; import java.util.List; class Solution { List<List<String>> result = new ArrayList<>(); List<String> path = new ArrayList<>(); public List<List<String>> partition(String s) { backtrack(s, 0); return result; } /** * 回溯分割 * @param s 目标字符串 * @param startIndex 起始分割位置 */ private void backtrack(String s, int startIndex) { // 终止条件：分割到字符串末尾 if (startIndex == s.length()) { result.add(new ArrayList<>(path)); return; } // 枚举所有可能的分割终点 for (int i = startIndex; i < s.length(); i++) { // 判断当前子串是否为回文串 if (isPalindrome(s, startIndex, i)) { path.add(s.substring(startIndex, i + 1)); backtrack(s, i + 1); path.remove(path.size() - 1); } } } /** * 判断子串是否为回文串 * @param s 字符串 * @param left 左边界 * @param right 右边界 * @return 是否为回文串 */ private boolean isPalindrome(String s, int left, int right) { while (left < right) { if (s.charAt(left) != s.charAt(right)) { return false; } left++; right--; } return true; } }

复杂度分析

• 时间复杂度：O (n×2ⁿ)，n 为字符串长度，最坏情况下每个位置都可以分割，且每次分割需要 O (n) 时间判断回文。
• 空间复杂度：O (n)，递归栈深度和路径的最大长度均为 n。

三、两道题的回溯模板对比

表格

四、二刷感悟：回溯题的 “两大核心”

1. 路径标记与恢复：单词搜索中通过修改矩阵标记访问，分割回文串中通过 startIndex 控制分割范围，本质都是为了避免重复访问或重复分割。
2. 剪枝优化：提前排除不符合条件的分支（如字符不匹配、子串非回文），能大幅减少递归次数，提升效率。

这两道题分别从二维矩阵和字符串两个场景，帮我们巩固了回溯的核心思想，掌握它们后，大部分中等难度的回溯题都能轻松应对。