# 132. Palindrome Partitioning II

[Link](https://leetcode.com/problems/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.
```

**Solution**

設計一個dp\[]，每個dp\[i] 表示 substring(0...i)裡面的最小cut數。

根據每個點mid向兩側(透過start, end pointers)進行expand看看是否可以成為palindrome， 假設可以形成回文，那就表示dp\[end]其中一個可能為 1 + dp\[start-1]，其中1表示s\[start....end]，因為它可以當成一個回文。\
考慮egde case， start == 0，表示s\[0....end]整串都是回文，那麼dp\[end]就是0

若start != 0 : dp\[end] = Math.min(dp\[end], dp\[start-1] + 1);

並考慮expand mid時，奇數長跟偶數長回文長度的可能

```
   public int minCut(String s) {
        int len = s.length();
        int[] dp = IntStream.range(0, len).toArray();
        
        for(int mid = 1; mid < len ; mid++ ){
            //expand from mid, assume it's length is odd
            for(int start = mid, end = mid; start >= 0 && end < len && s.charAt(start) == s.charAt(end);
               start--, end++){
                //minCutOf[0.....start-1] + 1(substring(start,end) would be one palindrome) -> 
                int newCutAtEnd = start == 0 ? 0 : dp[start-1] + 1;
                dp[end] = Math.min(dp[end], newCutAtEnd);
            }
            //expand from mid assume it's length is even
            for(int start = mid-1, end = mid; start>=0 && end < len &&s.charAt(start) == s.charAt(end);
               start--, end++){
                int newCutAtEnd = start == 0 ? 0 : dp[start-1] + 1;
                dp[end] = Math.min(dp[end], newCutAtEnd);
                
            }
        }
        return dp[len-1];

    }
    
```
