132. Palindrome Partitioning II

Posted on | In | 浏览 次
Words count in article: 800 | Reading time ≈ 3

题目

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.

解题思路

  • 本题给出一个字符串，求出将该字符串最少分割多少次可以实现其分割后的子串都是回文串
  • 本题求解比较复杂，主要思路是先求字符串某个区间内的子串是否是回文串然后，如果是说明可以被分割，否则不能被进行分割(因为分割以后也不是回文串，需要继续被分割)
  • 本题使用isPal[i,j]记录字符串在[i,j]是否是一个回文串，使用cut[i]记录字符串在区间[i, size]被分割后所有子串都为回文串需要被分割多少次，因此我们需要分类进行讨论，假设当前的区间为[i,j]
    • 首先需要对区间[i,j]是否是一个回文串进行判断
      • i < j
        • 不满足区间的基本要求
      • i == j
        • 显然是一个回文串，isPal[i,j] = true
      • j == i+1
        • 如果s[i] == s[j]，则这也是回文串，即isPal[i,j] = true，否则不是一个回文串
      • i+1 < j
        • 这部分判断比较麻烦，我们利用动态规划的思想，如果在区间[i+1,j-1]的子串是一个回文串，那么如果s[i] == s[j]的话，则该子串也是一个回文串，即isPal[i,j] = true，否则的话不是
    • 判断完该区间的子串是否是回文串后，我们需要对cut[i]进行更新。如果[i,j]是一个回文串(isPal[i,j] == true)的话，说明我们对于区间[i, size)有了一个新的分割方法，即在原基础上变成[i, j] + [j+1, size)，因此我们可以更新cut[i]
      • cut[i] = min(cut[i], cut[j+1] + 1)
      • 此处将原区间[i, j]分割成[i, j] + [j+1, size)两部分，需要在c[j+1]次的基础上再加一次分割操作，即分割次数为c[j+1]+1，但是我们需要注意的一点是对于第一次分割即[size-1, size)区间操作，其实分割次数是0，不需要对其进行分割，但是为了写法统一还是加1，后面的操作也不断使用到本次分割，因此对于每次的cut[i]都比实际多了1。因此最后返回字符串最小分割次数时候，即分割区间[0, size)的分割次数为cut[0]-1

实现代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    int minCut(string s) {
        if(s.size() <= 1)	return 0;

        // 判断区间[i, j]的字符是否是回文串
        bool isPal[s.size()][s.size()];

        // 记录区间[i, size]需要切割的次数
        int cut[s.size()+1];
        cut[s.size()] = 0;
        for(int i = s.size()-1; i >= 0; --i) {
            cut[i] = INT_MAX;
            for(int j = i; j < s.size(); ++j) {
                isPal[i][j] = false;
                if(i == j || i+1 == j && s[i] == s[j] || i+1 < j && isPal[i+1][j-1] && s[i] == s[j]) {
                    isPal[i][j] = true;
                    cut[i] = min(cut[i], cut[j+1] + 1);
                }
            }
        }
        return cut[0]-1;
    }
};