LeetCode: 132. Palindrome Partitioning II

题目描述

Given a string s, partition s such that every substring of the partition is a palindrome.
Return the minimum cuts needed for a palindrome partitioning of s.

Example:
Input: "aab"
Output: 1
Explanation: The palindrome partitioning [“aa”,”b”] could be produced using 1 cut.

解题思路 —— 动态规划构建回文表格， 动态规划计算最小切割数

动态规划构建回文表格

见 LeetCode: 131. Palindrome Partitioning 题解。

动态规划计算最小切割数

经过第一步操作，该问题转换为“已知字符串 s 的切割方式，求其最小切割数”。

1. 定义。记，minCutNum[i] 为“字符串 s 的前 i 个字符构成回文串的最小切割数”。
2. 初始化。将 minCutNum[i] 置为无穷大。如果 s 的前 i 个字母是回文串，则不用切割。即，若 bPalindromes[0][i] == true， 则 minCutNum[i] = 0。
3. 状态转移方程。 如果字符串 s 的区间 [i, j) 的子串是回文串， 则可能将该字符串切割为 [0, i) 和 [i, j) 两部分子串。 因此， minCutNum[j] = min{ minCutNum[i]+1 } , i 取 [1, j), 且 bPalindromes[i][j] == true;

AC 代码

class Solution {
private:
    // 根据待处理字符串 s 构造回文表格（bPalindromes）
    void ConstructPalindromesTable(vector<vector<bool>>& bPalindromes, const string& s)
    {     
        // initializing...
        bPalindromes.resize(s.size()+1);
        for(size_t i = 0; i < s.size()+1; ++i)
        {
            bPalindromes[i].resize(s.size()+1, false);
        }
        // s 串中的单个字符 [i, i+1) 一定是回文的
        // 定义空串 [i, i） 也是回文的
        for(size_t i = 0; i < s.size(); ++i)
        {
            bPalindromes[i][i+1] = true;
            bPalindromes[i][i] = true;
        }

        for(size_t j = 1; j < s.size()+1; ++j)
        {
            for(size_t i = 0; i < j; ++i)
            {
                // [i, j) 是回文串的充要条件: [i+1, j-1) 是回文串，且 s[i] == s[j-1]
                if(bPalindromes[i+1][j-1] == true && s[i] == s[j-1])
                {
                    bPalindromes[i][j] = true;
                }
            }
        }
    }

    // 根据回文表格 (bPalindromes) 计算最小切割数
    int minCutByBPalindromes(const vector<vector<bool>>& bPalindromes)
    {
        // minCutNum[i]: 字符串 s 的前 i 个字符构成回文串的最小切割数
        vector<int> minCutNum(bPalindromes.size(), INT_MAX);

        for(size_t j = 0; j < bPalindromes.size(); ++j)
        {
            // 前 j 个字符就是回文的，不用切割
            if(bPalindromes[0][j])
            {
                minCutNum[j] = 0;
                continue;
            }

            // 遍历可能切割的位置（在 i 点切割）
            for(size_t i = 1; i < j; ++i)
            {
                // [0, i) + [i, j) = [0, j)
                if(bPalindromes[i][j] && minCutNum[i]+1 < minCutNum[j])
                {
                    minCutNum[j] = minCutNum[i]+1;
                }
            }
        }

        return minCutNum.back();
    }
public:
    int minCut(string s) 
    {
        vector<vector<bool>> bPalindromes;
        // 根据待处理字符串 s 构造回文表格（bPalindromes）
        ConstructPalindromesTable(bPalindromes, s);
        // 根据回文表格 (bPalindromes) 计算最小切割数
        return minCutByBPalindromes(bPalindromes);
    }
};