# [LeetCode 132. Palindrome Partitioning II ](https://leetcode.com/explore/challenge/card/august-leetcoding-challenge-2021/613/week-1-august-1st-august-7th/3872/)
### Daily challenge Aug 7, 2021 (HARD)

>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.

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

:::info
**Example 2:**
**Input:** s = "a"
**Output:** 0
:::

:::info
**Example 3:**
**Input:** s = "ab"
**Output:** 1
:::

:::warning
**Constraints:**
* 1 <= s.length <= 2000
* s consists of lower-case English letters only.
:::

---

### Approach 1 : DP :book:
**`8 ms ( 98.08% )`** **`O(N^2)`**

* **`cut[i]`** 表示 `s[0...i]` 的 `minimum cuts`。
**`is_palindrome[i][j]`** 表示 `s[i...j]` 是否為 `palindrome`。
**`MIN`** 紀錄當前 `i` 的 `minimum cuts`，最後存入 `cut[i]`。
1. 首先 **`MIN = i`** 暫時表示所有字母皆不同，所以總共需要 `i cuts`。
2. 接著判斷 **`s[j] == s[i] && (j + 1 > i - 1 || is_palindrome[j+1][i-1])`**。
> * 只有 **`s[j] == s[i]`** 時，才有可能出現 palindrome 的情況。
> ---> 所以再判斷 **`is_palindrome[j+1][i-1]`**，也就要夾在 `i、j` 之間的字串是否為 palindrome。
> ---> **`j + 1 > i - 1`** 則表示兩個情況，一個是 `i == j`、一個是 `i、j 相鄰`。
> * 如果符合上述條件
>> 1. **`is_palindrome[j][i] = true`** ---> 表示 `s[j...i]` 是 palindrome。
>> 2. **`MIN = (j == 0) ? 0 : min(MIN, cut[j-1] + 1)`** -> 紀錄 `minimum cuts`。
>> ---> 如果 `j==0`，表示左邊沒有其他字母，也就是說 `s[0...i]` 整段就是 palindrome，所以 `cut = 0`。
>> ---> 其餘就比較 **`min(MIN, cut[j-1] + 1)`**。
>>

class Solution {
public:
    int minCut(string s) {
        int size = s.length();
        int cut[size];
        bool is_palindrome[size][size];
        memset(is_palindrome, false, sizeof(is_palindrome));
        
        for(int i=0; i<size; i++){
            int MIN = i;
            for(int j=0; j<=i; j++){
                if(s[j] == s[i] && (j + 1 > i - 1 || is_palindrome[j+1][i-1])){
                    is_palindrome[j][i] = true;
                    MIN = (j == 0) ? 0 : min(MIN, cut[j-1] + 1);
                }
            }
            cut[i] = MIN;
        }
        
        return cut[size-1];
    }
};