LeetCode 中等难度 | 回溯法进阶题解：单词搜索 分割回文串

目录一、单词搜索LeetCode 79题目描述解题思路Java 代码实现复杂度分析易错点 优化点二、分割回文串LeetCode 131题目描述解题思路Java 代码实现复杂度分析易错点 优化点三、回溯法进阶技巧总结一、单词搜索LeetCode 79题目描述给定一个m x n二维字符网格board和一个字符串单词word。如果word存在于网格中返回true否则返回false。单词必须按照字母顺序通过相邻的单元格内的字母构成其中 “相邻” 单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。示例plaintext输入board [[A,B,C,E],[S,F,C,S],[A,D,E,E]], word ABCCED 输出true解题思路这道题的核心是DFS 回溯本质是在二维网格中进行深度优先搜索寻找符合条件的路径遍历起点遍历网格中的每个单元格若单元格字符与单词首字符相同则以该单元格为起点开始 DFSDFS 过程从当前单元格出发向上下左右四个方向搜索匹配单词的下一个字符标记访问为避免重复使用单元格在访问时将单元格临时标记为#或其他特殊字符回溯时恢复终止条件若当前匹配的字符索引等于单词长度说明已找到完整单词返回true若单元格越界、字符不匹配或已被访问返回false。Java 代码实现java运行public class WordSearch { public boolean exist(char[][] board, String word) { int rows board.length; int cols board[0].length; // 遍历网格中的每个单元格作为起点 for (int i 0; i rows; i) { for (int j 0; j cols; j) { // 若起点字符与单词首字符相同开始DFS if (board[i][j] word.charAt(0) dfs(board, i, j, word, 0)) { return true; } } } return false; } /** * DFS搜索单词路径 * param board 二维网格 * param i 当前行索引 * param j 当前列索引 * param word 目标单词 * param index 当前匹配的单词字符索引 * return 是否找到单词路径 */ private boolean dfs(char[][] board, int i, int j, String word, int index) { // 终止条件匹配到单词末尾返回true if (index word.length()) { return true; } // 终止条件越界、字符不匹配或已被访问返回false 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, i 1, j, word, index 1) || dfs(board, i - 1, j, word, index 1) || dfs(board, i, j 1, word, index 1) || dfs(board, i, j - 1, word, index 1); // 回溯恢复当前单元格的字符 board[i][j] temp; return found; } }复杂度分析时间复杂度O(m×n×4L)其中m和n是网格的行数和列数L是单词长度。每个单元格作为起点最多有 4 个方向的分支递归深度为L空间复杂度O(L)递归栈的深度最多为单词长度L。易错点 优化点访问标记必须临时修改单元格字符标记访问回溯时恢复否则会影响后续搜索剪枝优化若当前字符不匹配直接返回false无需继续搜索提前终止找到完整单词后直接返回true避免不必要的搜索。二、分割回文串LeetCode 131题目描述给你一个字符串s请你将s分割成一些子串使每个子串都是回文串。返回s所有可能的分割方案。回文串是正着读和反着读都一样的字符串。示例plaintext输入s aab 输出[[a,a,b],[aa,b]]解题思路这道题的核心是回溯 预处理回文判断通过枚举分割点生成所有可能的回文分割方案预处理回文先用动态规划预处理字符串记录任意子串s[i..j]是否为回文串避免每次递归都判断回文提升效率回溯枚举分割点从字符串s的起始位置出发枚举每个位置作为分割点判断子串s[start..i]是否为回文递归与回溯若子串是回文将其加入当前路径递归处理剩余子串递归结束后回溯移除路径中的子串终止条件当分割点到达字符串末尾时将当前路径加入结果集。Java 代码实现java运行import java.util.ArrayList; import java.util.List; public class PartitionPalindrome { ListListString result new ArrayList(); ListString path new ArrayList(); boolean[][] isPalindrome; // 预处理回文数组 public ListListString partition(String s) { int n s.length(); // 预处理判断所有子串是否为回文 isPalindrome new boolean[n][n]; preprocessPalindrome(s, n); // 回溯枚举分割点 backtrack(s, 0); return result; } /** * 预处理回文子串 * param s 原字符串 * param n 字符串长度 */ private void preprocessPalindrome(String s, int n) { // 单个字符都是回文 for (int i 0; i n; i) { isPalindrome[i][i] true; } // 长度为2的子串 for (int i 0; i n - 1; i) { isPalindrome[i][i 1] (s.charAt(i) s.charAt(i 1)); } // 长度大于2的子串 for (int len 3; len n; len) { for (int i 0; i n - len; i) { int j i len - 1; isPalindrome[i][j] (s.charAt(i) s.charAt(j)) isPalindrome[i 1][j - 1]; } } } /** * 回溯枚举分割点 * param s 原字符串 * param start 当前分割的起始位置 */ private void backtrack(String s, int start) { // 终止条件分割点到达字符串末尾保存当前路径 if (start s.length()) { result.add(new ArrayList(path)); return; } // 枚举分割点从start到s.length()-1 for (int i start; i s.length(); i) { // 若子串s[start..i]是回文串 if (isPalindrome[start][i]) { // 做选择将回文子串加入路径 path.add(s.substring(start, i 1)); // 递归处理剩余子串分割点更新为i1 backtrack(s, i 1); // 回溯移除路径中的最后一个子串 path.remove(path.size() - 1); } } } }复杂度分析时间复杂度O(n×2n)其中n是字符串长度。预处理回文的时间为O(n2)回溯过程中字符串有2n−1种分割方式每种方式需要O(n)时间生成子串空间复杂度O(n2n)预处理回文数组占用O(n2)空间递归栈深度和路径存储的最大长度为O(n)。易错点 优化点预处理回文动态规划预处理可将回文判断的时间复杂度从O(n)降至O(1)大幅提升整体效率分割点枚举必须从start开始枚举分割点避免重复分割路径拷贝将路径加入结果集时必须创建新的ArrayList否则后续修改会影响结果。三、回溯法进阶技巧总结这两道题让我们看到了回溯法的更多应用场景也掌握了两个进阶技巧结合 DFS在二维网格、图等结构中通过 DFS 实现回溯标记访问状态避免重复预处理优化对于重复判断的条件如回文先通过动态规划预处理将单次判断的时间复杂度降至O(1)减少无效递归。回溯法的核心依然是 “枚举 剪枝”但在不同场景下需要结合问题特点灵活调整网格 / 图搜索需要标记访问状态防止循环和重复访问字符串分割可通过预处理减少重复判断提升效率。