0131. Palindrome Partitioning ============================= 题目信息 -------- :题号: 0131. 分割回文串 :难度: Medium :主题: 字符串、回溯、区间动态规划、结果枚举 :原题: `LeetCode 0131 `_ :重点: 用起始下标表示未覆盖后缀,回溯枚举合法下一段,并预处理区间回文性以删除跨分支重复比较 题目重述 -------- 给定字符串 ``s``,在字符之间选择若干切点,把它分成一组连续、非空片段。返回所有满足“每个片段都是 回文串”的完整切分方案。片段必须保持原顺序并恰好覆盖整个字符串,答案顺序不限。 自建示例 -------- * ``s = "abba"``:合法方案为 ``["a", "b", "b", "a"]``、``["a", "bb", "a"]`` 和 ``["abba"]``; * ``s = "abc"``:没有长度大于一的回文片段,唯一方案是 ``["a", "b", "c"]``; * ``s = "aaa"``:``["a", "a", "a"]``、``["a", "aa"]``、``["aa", "a"]``、``["aaa"]`` 都合法,说明相同内容出现在不同位置时仍代表不同切分选择。 C++ 实现 -------- .. code-block:: cpp #include #include class Solution { private: bool isPalindrome(const std::string& s, int left, int right) { while (left < right) { if (s[left] != s[right]) { return false; } ++left; --right; } return true; } void searchWithRepeatedChecks( const std::string& s, int start, std::vector& path, std::vector>& answer ) { if (start == static_cast(s.size())) { answer.push_back(path); return; } for (int end = start; end < static_cast(s.size()); ++end) { if (!isPalindrome(s, start, end)) { continue; } path.push_back(s.substr(start, end - start + 1)); searchWithRepeatedChecks(s, end + 1, path, answer); path.pop_back(); } } std::vector> buildPalindromeTable( const std::string& s ) { const int length = static_cast(s.size()); std::vector> palindrome( length, std::vector(length, false) ); for (int left = length - 1; left >= 0; --left) { for (int right = left; right < length; ++right) { const bool shortInterval = right - left <= 2; palindrome[left][right] = s[left] == s[right] && (shortInterval || palindrome[left + 1][right - 1]); } } return palindrome; } void searchWithTable( const std::string& s, int start, const std::vector>& palindrome, std::vector& path, std::vector>& answer ) { if (start == static_cast(s.size())) { answer.push_back(path); return; } for (int end = start; end < static_cast(s.size()); ++end) { if (!palindrome[start][end]) { continue; } path.push_back(s.substr(start, end - start + 1)); searchWithTable(s, end + 1, palindrome, path, answer); path.pop_back(); } } public: std::vector> partition(std::string s) { const auto palindrome = buildPalindromeTable(s); std::vector> answer; std::vector path; searchWithTable(s, 0, palindrome, path, answer); return answer; } }; 题解 ---- 从所有切缝的选择开始 ~~~~~~~~~~~~~~~~~~~~ 长度为 ``n`` 的字符串有 ``n-1`` 个字符间隙,每个间隙都可以切或不切,因此原始切分空间有 ``2^(n-1)`` 种。先生成所有切点组合,再逐段验证回文虽然完整,却会保留大量早已包含非回文段的无效后缀 选择;例如前一段确定为 ``"ab"`` 后,无论后面怎样切都不可能成为合法答案。 更有效的搜索状态是 ``start``:``s[0..start-1]`` 已被 ``path`` 中的回文片段完整、无重叠地覆盖, ``s[start..n-1]`` 仍待切分。下一步只需枚举第一段的结束位置 ``end``;若 ``s[start..end]`` 不是回文, 整类以它开头的切分直接删除,只有合法片段才进入递归。 位置图解释为何不会重漏 ~~~~~~~~~~~~~~~~~~~~~~ 把 ``0..n`` 这 ``n+1`` 个字符边界看成节点。若 ``s[start..end]`` 是回文,就有一条从 ``start`` 到 ``end+1`` 的有向边。下标每次严格增大,所以这是一张 DAG;从 ``0`` 到 ``n`` 的每条路径恰好对应一组 合法切分。 任意合法方案的第一段都有唯一终点,外层循环会选择它,之后对剩余后缀重复同样论证,因此不会漏;两个 不同方案至少有一个切点不同,对应的边序列也不同,因此不会重复。 方案一:搜索时现查回文 ~~~~~~~~~~~~~~~~~~~~~~ ``searchWithRepeatedChecks`` 在需要区间时用双指针从两端向内比较。这比生成所有切分后再验证更早剪枝,且 代码与回文定义直接对应。不过同一区间的回文性可能被不同路径反复询问;一次检查最长 ``O(n)``,而它只由 两个端点决定,与此前选过哪些片段无关。 例如 ``"aaaa..."`` 具有大量合法前缀,不同切分分支会多次来到相同 ``start``,再对同一批 ``[start, end]`` 区间执行完全相同的字符比较。这部分判断可以在搜索前一次性共享。 区间状态怎样从短区间生成长区间 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ 令 ``palindrome[left][right]`` 表示闭区间 ``s[left..right]`` 是否回文。两端相等,并且内部也是回文时, 整个区间才是回文: .. code-block:: text palindrome[left][right] = s[left] == s[right] && (right - left <= 2 || palindrome[left + 1][right - 1]) 长度一和长度二可直接由两端判断;代码把长度三也放进 ``right - left <= 2``,因为两端相等时中间单字符 必为回文。对更长区间,依赖项的左端更大,所以 ``left`` 必须从右向左;同一 ``left`` 下,``right`` 从 左向右即可。若反向计算 ``left``,读取 ``palindrome[left+1][right-1]`` 时可能仍是默认值。 回溯路径的不变量 ~~~~~~~~~~~~~~~~ ``searchWithTable`` 进入函数时,``path`` 恰好覆盖 ``[0, start)``。选择 ``[start, end]`` 后追加对应子串, 不变量对 ``end+1`` 成立;子调用返回后必须弹出同一片段,恢复父状态再尝试下一个终点。到达 ``start == n`` 时没有未覆盖字符,此时复制 ``path`` 才形成一条完整答案。 具体走读 ``abba``: .. list-table:: :header-rows: 1 * - ``start`` 与当前路径 - 表中可选下一段 - 后续结果 * - ``0``,``[]`` - ``"a"``、``"abba"`` - 产生一个后缀分支和一个直接完成分支 * - ``1``,``["a"]`` - ``"b"``、``"bb"`` - 分别进入 ``start=2`` 与 ``start=3`` * - ``3``,``["a", "bb"]`` - ``"a"`` - 到达 ``4``,保存 ``["a", "bb", "a"]`` * - ``4``,``["abba"]`` - 无需再选 - 复制完整方案 表中 ``"ab"``、``"abb"`` 为假,所以搜索树根本不会生成以这些非回文前缀开头的分支。 主解选择与复杂度 ~~~~~~~~~~~~~~~~ 公开入口采用“区间 DP 预处理 + 回溯”。它用 ``O(n^2)`` 时间和空间换取每次回文判断 ``O(1)``,删除了 跨分支的重复字符比较;直接检查法省去表空间,更适合字符串很短且合法分支稀少的场景,因此作为有明确 取舍的基线保留。 合法方案数本身可能是指数级,任何返回全部答案的算法都无法避开输出成本。预处理为 ``O(n^2)``;搜索中 每条路径深度最多 ``n``,创建子串和复制答案的总时间与实际生成内容成正比。除返回结果和回文表外,递归栈 与当前路径占 ``O(n)``。