跳到主要内容

LeetCode 131. 分割回文串

本节目标

枚举切分终点，并只把回文片段加入当前分割路径。

这道题是约束型回溯中“切分位置 + 局部合法性”的母题。每一层只决定当前片段在哪里结束；能否继续递归由新增片段是否为回文决定。

查看 LeetCode 原题

题意与约束​

给定字符串 s，把它切成若干非空子串，返回所有使每个子串都是回文串的分割方案。不同切分位置产生不同方案；例如 aab 的合法结果是 a | a | b 与 aa | b。

朴素思路与瓶颈​

字符串长度为 n 时，相邻字符之间有 n - 1 个可能的切口。先枚举所有切法，再逐段检查回文，虽然正确，却会把含有明显非回文片段的分支一直走到叶子。

状态与剪枝​

令 start 为下一段的起点。枚举 end 从 start 到末尾：若 s[start..end] 不是回文，当前候选不可能属于任何合法答案，立刻跳过；若是回文，就把该片段放入 path，递归处理 end + 1。

当 start 到达字符串末尾时，path 中每一段都已在加入时验证过，且它们首尾相接覆盖原字符串，因此直接复制为一个答案。回溯时弹出最后一段，使下一个 end 在同一前缀下重新尝试。

正确性依据​

每个递归节点唯一对应一个已经验证为回文的前缀分割。循环枚举该状态下所有可能的下一段终点，因而不会漏掉任何合法切分；非回文候选在进入递归前被排除，不会产生非法答案。到达末尾的路径拼接回原串，且每段均经过验证，所以记录的答案正确。每个合法分割都按其切分终点依次被选择，故一定会被枚举到。

代码实现​

C++17
#include <string>
#include <vector>

using namespace std;

class Solution {
private:
    vector<vector<string>> partitions;
    vector<string> path;

    bool isPalindrome(const string& value, int left, int right) {
        while (left < right) {
            if (value[left] != value[right]) {
                return false;
            }
            left++;
            right--;
        }
        return true;
    }

    void backtrack(const string& value, int start) {
        if (start == static_cast<int>(value.size())) {
            partitions.push_back(path);
            return;
        }

        for (int end = start; end < static_cast<int>(value.size()); end++) {
            if (!isPalindrome(value, start, end)) {
                continue;
            }
            path.push_back(value.substr(start, end - start + 1));
            backtrack(value, end + 1);
            path.pop_back();
        }
    }

public:
    vector<vector<string>> partition(string s) {
        partitions.clear();
        path.clear();
        backtrack(s, 0);
        return partitions;
    }
};

复杂度分析​

设字符串长度为 n，合法分割的输出总字符数为 R。最坏情况下回文切分数呈指数增长；搜索树的节点数为指数级。当前实现每次回文检查最多比较 O(n) 个字符，因此搜索部分最坏为 O(n · 2^n)，复制所有答案还需 O(R) 时间。递归栈和当前路径最多 O(n)，不计答案的额外空间为 O(n)。

易错点​

  • 只在完整切分后再判断所有片段，会丢失局部剪枝。
  • end 不包含在片段中，或递归仍从 end 开始，都会造成漏字符或无限递归。
  • 将 path 本身直接保存到答案，之后回溯修改会污染已经记录的方案。
  • 把空字符串当作一个非空片段加入路径；空输入的唯一分割是空路径。

模式迁移​

任何“按位置切分并要求每段满足性质”的题都可沿用这个状态：分割 IP 地址时检查段范围，拆分单词时检查字典成员，表达式加括号时检查运算边界。关键是让下一段的局部判断发生在递归之前。