# 132. Palindrome Partitioning II

{% hint style="info" %}
This link is the best solution improvement pathway.

<https://leetcode.com/problems/palindrome-partitioning-ii/discuss/668367/Java-3-Versions-Of-The-Solusions.-Easy-to-understand!!>
{% endhint %}

### Solution:

1. Initilize `p[i][j] = False`, which represents whether the substring `[i:j]` of the string is palindrome.
2. Initilize `minCut[i] = i`, which represents the minimum cut of the substring ends at `i`.
3. If `p[i][j] = True`, then `minCut[i] = min(minCut[i], minCut[j-1] + 1)`. We can find at least one palindrome until index of i, because any character is palindrome.
4. Return `minCut[len(s)-1]`

{% tabs %}
{% tab title="Python" %}

```python
class Solution:
    def minCut(self, s: str) -> int:
        p = [[False]*len(s) for i in range(len(s))]
        minCut = [i for i in range(len(s))]
        # self.isPalin(s, p)
        
        for i in range(1, len(s)):
            for j in range(0, i+1):
                if s[i] == s[j] and (j+1 >= i-1 or p[j+1][i-1] == True):
                    p[j][i] = True
                    if j == 0:
                        minCut[i] = 0
                        break
                    else:
                        minCut[i] = min(minCut[i], minCut[j-1]+1)
        
        return minCut[len(s)-1]
        
  # 计算 string 中从 j 到 i 是否是回文，用p[j][i]表示      
    def isPalin(self, s, p):
        for i in range(len(s)):
            for j in range(i+1):
                if i == j: 
                    p[j][i] = True
                else:
                    if s[j] == s[i]:
                        if j+1 >= i-1 or p[j+1][i-1] == True:
                            p[j][i] = True


```

{% endtab %}

{% tab title="Java(O(n^2)" %}

```java
class Solution {
    public int minCut(String s) {
        int[] minCut = new int[s.length()];
        for(int i = 0; i < s.length(); i ++) {
            minCut[i] = i;
        }
        
        boolean[][] palind = new boolean[s.length()][s.length()];
        
        fillPalind(s, palind);
        
        for(int i = 1; i < s.length(); i ++)
            for(int j = 0; j <= i; j ++) {
                if(palind[j][i]) {
                    if(j == 0) {
                        minCut[i] = 0;
                        break;
                    } else {
                        minCut[i] = Math.min(minCut[i], minCut[j-1]+1);
                    }
                }
            }
        return minCut[s.length() - 1];
    }
    
    private void fillPalind(String s, boolean[][] palind) {
        for(int i = 0; i < s.length(); i ++)
            for(int j = 0; j <= i; j ++ ) {
                if(i == j)
                    palind[j][i] = true;
                else if(s.charAt(j) == s.charAt(i)) {
                    if(j+1 >= i-1 || palind[j+1][i-1] == true)
                        palind[j][i] = true;
                }
            }
    }
}      
```

{% endtab %}
{% endtabs %}

这里有两部需要注意的：

第一步：计算一个string所有子字符串是否是回文。优化一：事先计算好所有的，这样的时间复杂度虽然是 $$O(n^2)$$ ，但是在第二步中只需要获取这步的结果，比直接在第二步的每次循环中去检查子字符串是否是回文用的时间复杂度 $$O(n^3)$$ 要快得多；优化二：用动态规划来计算是否为回文的矩阵，如果这个字符串开头与结尾字符相等，并且中间的字符串为回文（根据之前的记录），那么这个子字符串就是回文；优化三：由于都是两层的循环，因此可以将计算回文与最小`cut`同步进行，这样节省了一倍的时间。

第二步：用动归计算从第一个字母开始的`[i:j]`最小`cut`，也就是说一个字符串，如果可以从中间切一刀，右半部分是回文，那么这个位置的`minCut`就是`cut`之前那个元素的`minCut`加一，循环来寻找最小值


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://r24zeng.gitbook.io/leetcode-notebook/wan-quan-an-zhao-jiu-zhang-suan-fa-shua-de-60-dao-zuo-you/ix.-dynamic-programming/132.-palindrome-partitioning-ii.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.