# LC 132. Palindrome Partitioning II

### [Problem link](https://leetcode.com/problems/palindrome-partitioning-ii/)

###### tags: `leedcode` `hard` `c++` `Two Pointer` `DP`

Given a string <code>s</code>, partition <code>s</code> such that every substring of the partition is a palindrome.

Return the **minimum** cuts needed for a palindrome partitioning of <code>s</code>.

**Example 1:**

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

**Example 2:**

Input: s = "a"
Output: 0

**Example 3:**

Input: s = "ab"
Output: 1

**Constraints:**

- <code>1 <= s.length <= 2000</code>
- <code>s</code> consists of lowercase English letters only.

## Solution 1 - Two Pointer & DP
#### C++

class Solution {
public:
    int minCut(string s) {
        vector<vector<bool>> isPalid(s.size(), vector<bool>(s.size(), false));
        for (int i = s.size() - 1; i >= 0; i--) {
            for (int j = i; j < s.size(); j++) {
                if (s[i] == s[j] && (j - i <= 1 || isPalid[i + 1][j - 1])) {
                    isPalid[i][j] = true;
                }
            }
        }

        // dp[i]: minimum cuts needed for a palindrome partitioning of s[0] ~ s[i]
        vector<int> dp(s.size(), s.size() - 1);
        for (int i = 0; i < dp.size(); i++) {
            dp[i] = i;
        }

        for (int i = 1; i < s.size(); i++) {
            for (int j = 0; j <= i; j++) {
                if (isPalid[j][i]) {
                    if (j == 0) {
                        dp[i] = 0;
                    } else {
                        dp[i] = min(dp[i], dp[j - 1] + 1);
                    }
                }
            }
        }
        return dp.back();
    }
};

>### Complexity
>n = s.length
>| | Time Complexity | Space Complexity |
>| ----------- | --------------- | ---------------- |
>| Solution 1 | O(n^2) | O(n^2) |

## Note
[Ref.](https://github.com/youngyangyang04/leetcode-master/blob/master/problems/0132.%E5%88%86%E5%89%B2%E5%9B%9E%E6%96%87%E4%B8%B2II.md)