目录一、LeetCode 79 单词搜索中等题目描述核心思路DFS 回溯 标记访问Java 完整实现复杂度分析二、LeetCode 131 分割回文串中等题目描述核心思路回溯 回文判断Java 完整实现复杂度分析三、两道题的回溯模板对比四、二刷感悟回溯题的 “两大核心”今天复盘两道经典回溯题它们都是DFS 回溯剪枝的典型代表分别是二维矩阵的路径搜索问题和字符串的分割问题掌握它们能帮你彻底吃透回溯题的核心模板和剪枝技巧。一、LeetCode 79 单词搜索中等题目描述给定一个m x n二维字符网格board和一个字符串单词word。如果word存在于网格中返回true否则返回false。单词必须按照字母顺序通过相邻的单元格内的字母构成其中 “相邻” 单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。核心思路DFS 回溯 标记访问这道题的核心是在二维矩阵中进行深度优先搜索需要注意遍历所有起点以矩阵中每个单元格为起点尝试匹配单词的第一个字符。标记访问为了避免重复访问同一个单元格访问时将当前单元格标记为特殊字符如#回溯时恢复。方向搜索每次搜索四个方向上下左右只要有一个方向能匹配后续字符就继续递归。剪枝优化如果当前字符与单词目标字符不匹配直接返回。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所有可能的分割方案。核心思路回溯 回文判断这道题是字符串分割问题核心是枚举所有可能的分割点并判断分割出的子串是否为回文串枚举分割点从字符串的startIndex位置开始尝试分割[startIndex, i]区间的子串。回文判断判断当前分割的子串是否为回文串如果是则加入路径继续递归处理剩余部分。回溯恢复递归结束后将当前子串从路径中移除尝试其他分割方式。Java 完整实现java运行import java.util.ArrayList; import java.util.List; class Solution { ListListString result new ArrayList(); ListString path new ArrayList(); public ListListString 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。三、两道题的回溯模板对比表格对比项79. 单词搜索131. 分割回文串问题类型二维矩阵路径搜索字符串分割枚举关键变量当前坐标 (i,j)、匹配索引 index起始分割位置 startIndex剪枝条件字符不匹配、越界子串不是回文串标记方式修改原矩阵标记访问无需额外标记通过 startIndex 控制终止条件匹配到单词末尾分割到字符串末尾四、二刷感悟回溯题的 “两大核心”路径标记与恢复单词搜索中通过修改矩阵标记访问分割回文串中通过 startIndex 控制分割范围本质都是为了避免重复访问或重复分割。剪枝优化提前排除不符合条件的分支如字符不匹配、子串非回文能大幅减少递归次数提升效率。这两道题分别从二维矩阵和字符串两个场景帮我们巩固了回溯的核心思想掌握它们后大部分中等难度的回溯题都能轻松应对。