LeetCode 132.Palindrome Partitioning II (分割回文串 II)

清疚 2022-05-08 10:04 183阅读 0赞

题目描述：

给定一个字符串 *s*，将 *s* 分割成一些子串，使每个子串都是回文串。

返回符合要求的最少分割次数。

**示例:**

输入: "aab"
    输出: 1
    解释: 进行一次分割就可将 s 分割成 ["aa","b"] 这样两个回文子串。

AC C++ Solution:

解题思路：

isPalin\[i\]\[j\] , which is whether s\[i..j\] forms a pal

minCuts\[i\], which is the minCut for s\[0..i-1\]

一种典型的解决方案是基于DP。这种解决方案首先构造一个二维bool数组isPalin，以指示子串s \[i..j\]是否是回文结构。要获得这样的数组，我们需要O（N ^ 2）时间复杂度。此外，为了获得最小切割，我们需要另一个数组minCuts来执行DP，minCuts \[i\]保存为子串s \[0..i-1\]找到的最小切割。minCuts \[i\]被初始化为i-1，这是所需的最大切割（将字符串切割成单字母字符），minCuts \[0\]最初设置为-1，这在s \[0 .. i-1\]是回文。当我们构造isPalin数组时，我们每次找到回文子字符串时都会更新minCuts，即如果s \[i..j\]是回文，则minCuts \[j + 1\]将更新为当前minCuts \[j\]的最小值+1\]和minCut \[i\] +1（即将s \[0..j\]切换为s \[0，i-1\]和s \[i，j\]）

代码：

// DP solution
        class Solution {
        public:
            int minCut(string s) {
                const int N = s.size();
                if(N<=1) return 0;
                int i,j;
                bool isPalin[N][N];
                fill_n(&isPalin[0][0], N*N, false);
                int minCuts[N+1];
                for(i=0; i<=N; ++i) minCuts[i] = i-1;
                
                for(j=1; j<N; ++j)
                {
                    for(i=j; i>=0; --i)
                    {
                        if( (s[i] == s[j]) && ( ( j-i < 2 ) || isPalin[i+1][j-1] ) )
                        {
                            isPalin[i][j] = true;
                            minCuts[j+1] = min(minCuts[j+1], 1 + minCuts[i]);    
                        }
                    }
                }
                return minCuts[N];
                
            }
        };