0132. Palindrome Partitioning II ================================ 题目信息 -------- :题号: 0132. 分割回文串 II :难度: Hard :主题: 字符串、动态规划、区间回文、前缀最优值 :原题: `LeetCode 0132 `_ :重点: 将全部切分路径压缩为每个前缀的最少切割,并用回文表把转移判断从线性降为常数时间 题目重述 -------- 给定非空字符串 ``s``,在字符间切若干刀,使每个得到的连续非空片段都是回文串。返回最少切割次数。若 整个字符串本身就是回文串,答案为 ``0``;切成 ``k`` 个片段只需要 ``k-1`` 刀。 自建示例 -------- * ``s = "racecarx"``:切成 ``"racecar" | "x"``,只需一刀; * ``s = "abacdc"``:切成 ``"aba" | "cdc"``,答案为 ``1``; * ``s = "aab"``:最优切分为 ``"aa" | "b"``,答案为 ``1``,逐字符切分的两刀不是最优; * ``s = "level"``:整串是回文,返回 ``0``。 C++ 实现 -------- .. code-block:: cpp #include #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; } int minimumPiecesFrom( const std::string& s, int start, std::vector& memo ) { if (start == static_cast(s.size())) { return 0; } if (memo[start] != -1) { return memo[start]; } int bestPieces = static_cast(s.size()) - start; for (int end = start; end < static_cast(s.size()); ++end) { if (isPalindrome(s, start, end)) { bestPieces = std::min( bestPieces, 1 + minimumPiecesFrom(s, end + 1, memo) ); } } memo[start] = bestPieces; return bestPieces; } int memoizedSuffixSearch(const std::string& s) { std::vector memo(s.size(), -1); return minimumPiecesFrom(s, 0, memo) - 1; } 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) { palindrome[left][right] = s[left] == s[right] && (right - left <= 2 || palindrome[left + 1][right - 1]); } } return palindrome; } int prefixDynamicProgramming(const std::string& s) { const int length = static_cast(s.size()); const auto palindrome = buildPalindromeTable(s); std::vector minimumCuts(length + 1, 0); minimumCuts[0] = -1; for (int end = 1; end <= length; ++end) { minimumCuts[end] = end - 1; for (int start = 0; start < end; ++start) { if (palindrome[start][end - 1]) { minimumCuts[end] = std::min( minimumCuts[end], minimumCuts[start] + 1 ); } } } return minimumCuts[length]; } public: int minCut(std::string s) { return prefixDynamicProgramming(s); } }; 题解 ---- 原始空间与“只求最优”的新信息 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~ 长度为 ``n`` 的字符串有 ``n-1`` 个潜在切缝,所有切分方案最多达到 ``2^(n-1)``。像上一题那样回溯能够 列出每条合法路径,再从中选片段最少的一条;但本题不要求方案内容,只要求一个最小值。许多不同前缀切法 到达同一后缀起点后,未来可选的回文片段完全相同,继续分别搜索是在重复解决同一个问题。 令状态 ``start`` 表示尚未处理的后缀 ``s[start..n-1]``。枚举它的第一段 ``s[start..end]``,只在该段为 回文时继续。``minimumPiecesFrom(start)`` 等于一加剩余后缀的最少片段数;同一个 ``start`` 的结果记忆一次, 就把指数路径树压缩成 ``n`` 个后缀状态。 方案一:记忆化后缀最少片段数 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~ ``minimumPiecesFrom`` 的终点 ``start == n`` 返回零,表示空后缀不再需要片段;非空状态最坏可逐字符切开, 所以 ``bestPieces`` 初值为剩余字符数。每个合法首段贡献一个片段,再接 ``end+1`` 后缀的最优值。 代码先算片段数,公开辅助方案最后减一得到切割数。这样递归终点自然,但每个状态仍要枚举 ``O(n)`` 个终点, 每次 ``isPalindrome`` 又可能比较 ``O(n)`` 个字符,最坏时间 ``O(n^3)``。记忆化删除了重复后缀搜索,却没 删除不同状态转移对区间回文性的重复判断。 回文表提供可共享的转移条件 ~~~~~~~~~~~~~~~~~~~~~~~~~~ 区间 ``[left, right]`` 为回文,当且仅当两端字符相等,并且区间长度不超过三或内部区间为回文: .. code-block:: text palindrome[left][right] = s[left] == s[right] && (right - left <= 2 || palindrome[left + 1][right - 1]) ``left`` 从右向左计算,保证更靠内的状态已经就绪。预处理花费 ``O(n^2)`` 后,每个候选最后片段是否回文 都能在 ``O(1)`` 时间确定。 从后缀递归改写为前缀最优 ~~~~~~~~~~~~~~~~~~~~~~~~ 主解令 ``minimumCuts[end]`` 表示前 ``end`` 个字符 ``s[0..end-1]`` 的最少切割。对每个 ``end``,枚举最后 一段的起点 ``start``;若 ``s[start..end-1]`` 是回文,前缀 ``[0, start)`` 的最优切法与最后一段之间增加 一刀: .. code-block:: text minimumCuts[end] = min(minimumCuts[start] + 1) 对所有回文 s[start..end-1] 最后一段确定后,它与更早的具体切点互不影响。如果前缀使用的不是最少切割,可以用更优前缀替换且保持 最后一段不变,所以只保存 ``minimumCuts[start]`` 不会丢失全局最优方案。 为何空前缀必须设为负一 ~~~~~~~~~~~~~~~~~~~~~~ ``minimumCuts[0] = -1`` 是对“片段数比切割数多一”的统一编码。若 ``s[0..end-1]`` 整段为回文,转移取 ``start = 0``,得到 ``-1 + 1 = 0``,恰好表示第一段前面不需要切刀。若把空前缀设为零,整串回文也会被 误算成一刀。 对非空前缀,逐字符切开最多需要 ``end-1`` 刀,因此代码以它初始化。这个上界也保证即使只找到单字符 回文,状态仍会得到合法答案。 具体走读 ``aab`` ~~~~~~~~~~~~~~~~ .. list-table:: :header-rows: 1 * - ``end`` 与前缀 - 可作最后一段的回文 - ``minimumCuts[end]`` * - ``0``,空前缀 - 不适用 - ``-1`` * - ``1``,``a`` - ``s[0..0] = "a"`` - ``-1 + 1 = 0`` * - ``2``,``aa`` - ``"a"``、``"aa"`` - 整段 ``"aa"`` 令结果为 ``0`` * - ``3``,``aab`` - 最后一段只能取 ``"b"`` - ``minimumCuts[2] + 1 = 1`` 这里无需保存 ``["a", "a", "b"]`` 与 ``["aa", "b"]`` 两条路径;前缀 ``aa`` 只留下切割数零,便足以 决定追加 ``b`` 后的最优值。 主解选择与复杂度 ~~~~~~~~~~~~~~~~ 公开入口采用二维回文表加一维前缀 DP,状态含义和计算顺序清楚,时间 ``O(n^2)``、空间 ``O(n^2)``。 记忆化后缀方案只需 ``O(n)`` 状态和递归栈,但由于即时回文检查最坏达到 ``O(n^3)``,保留它是为了展示 从答案枚举到最优值状态压缩的第一步,而非主解。返回方案本身不在题目要求中,所以代码完全删除了路径 数组与回溯复制。