LeetCode 131. 分割回文串

题目描述给定一个字符串s将它分割成若干子串使每个子串都是回文串返回所有可能的分割方案。例如输入s aab 输出[[a,a,b],[aa,b]]初始思路一开始想到使用滑动窗口先固定一个长度k再按照这个长度依次截取子串。如果截取出的字符串是回文串就把它加入答案。这种思路可以找到部分等长切分却无法表示题目要求的所有方案。例如s aab两个合法方案分别是[a, a, b] [aa, b]第一种方案的子串长度是1、1、1第二种方案的子串长度是2、1。固定窗口长度k之后同一条分割路径中的每一段只能等长因此会漏掉长度不同的组合。这道题真正需要枚举的不是窗口长度而是每一步的切割位置。解题思路使用回溯从尚未分割的位置start开始枚举当前子串的结束位置end。定义递归函数dfs(start)它表示s[0, start) 已经完成分割现在从 start 开始继续寻找合法方案对于每一个end当前候选子串是s[start, end]如果它是回文串就可以做出本层选择1. 将 s[start, end] 加入 path 2. 从 end 1 继续分割 3. 递归返回后将该子串从 path 中移除如果start s.length()说明整个字符串已经分割完毕并且path中每一段都经过了回文判断此时将当前路径加入答案。以s aab为例搜索过程可以简化为从下标 0 开始 ├── 选择 a │ └── 从下标 1 开始 │ ├── 选择 a │ │ └── 选择 b - [a, a, b] │ └── ab 不是回文串 └── 选择 aa └── 从下标 2 开始 └── 选择 b - [aa, b]代码实现class Solution { public ListListString partition(String s) { ListListString ans new ArrayList(); ListString path new ArrayList(); dfs(s, 0, path, ans); return ans; } private void dfs( String s, int start, ListString path, ListListString ans) { if (start s.length()) { ans.add(new ArrayList(path)); return; } for (int end start; end s.length(); end) { if (!isPalindrome(s, start, end)) { continue; } path.add(s.substring(start, end 1)); dfs(s, end 1, path, ans); path.remove(path.size() - 1); } } 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; } }为什么回溯能够枚举所有方案对于位置start循环会依次尝试所有可能的结束位置for (int end start; end s.length(); end)因此当前子串可能是s[start, start] s[start, start 1] s[start, start 2] ...只有当前子串是回文串时才会递归处理剩余部分。这样既不会遗漏某个切割位置也不会让非回文子串进入最终答案。path记录的是一条正在搜索的分割路径。递归结束后执行path.remove(path.size() - 1);可以撤销本层选择让下一次循环尝试另一个结束位置。为什么滑动窗口不适合这道题滑动窗口通常维护一个连续区间并根据条件移动左右边界适合寻找最长、最短或满足某种性质的单个区间。这道题要求返回所有分割方案。每确定一个子串后剩余字符串还可能有多种切法因此搜索过程会产生多个分支。两者的状态结构不同滑动窗口移动边界维护一个区间 回溯枚举切点保留一条路径并继续搜索剩余部分固定长度k只能处理等长切分而回溯中的end会在每一层重新枚举所以同一条路径中的子串长度可以不同。易错点1. 使用固定长度 k 分割固定k后每次都截取长度相同的子串会漏掉混合长度的分割方案。应该用start表示当前起点并在当前层枚举所有end。2. 判断了整个字符串是否回文每次需要判断的是当前候选子串s[start, end]不是原字符串s。如果始终判断整个s就无法决定当前这一刀是否可以切下去。3. substring 的方法名和右边界Java 中的方法名是substring(beginIndex, endIndex)不是subString。同时endIndex是左闭右开的右边界。要截取包含下标end的子串需要写s.substring(start, end 1)如果调用s.substring(i, i k)必须保证i k s.length()否则会抛出StringIndexOutOfBoundsException。4. 找到答案时没有复制 path不能直接写ans.add(path);因为path后续还会被修改。应该保存它当前状态的副本ans.add(new ArrayList(path));5. 递归后没有撤销选择加入当前子串后递归返回时必须将它移除path.add(part); dfs(...); path.remove(path.size() - 1);否则上一条路径中的子串会残留到下一条路径中。复杂度分析长度为n的字符串一共有n - 1个潜在切割位置每个位置都可能切或不切因此分割方案数量最多达到2^(n - 1)。时间复杂度O(n * 2^n)。需要搜索指数级分割方案构造每个答案最多需要O(n)时间。辅助空间复杂度O(n)。递归深度和当前路径最多都是n。如果计算返回结果答案本身还需要O(n * 2^n)空间。复盘这次的关键问题是把“分割”理解成了固定窗口切片。看到“返回所有可能的分割方案”时应该优先想到每个位置都可能成为切点需要用回溯枚举不同选择。这题的递归状态可以记为start 表示下一段从哪里开始 end 表示当前这一段在哪里结束 path 表示已经选出的回文子串每一层的完整过程是枚举结束位置 - 检查回文 - 加入路径 - 递归剩余部分 - 撤销选择Tips遇到字符串分割问题可以先问自己1. 每一段的长度是否固定 2. 题目是否要求所有分割方案 3. 当前递归应该从哪个位置继续切 4. substring 的右边界是否可能越界对于这题可以记住一句话从 start 枚举 end当前段是回文就继续切递归返回后撤销当前段。