# 131. Palindrome Partitioning

{% hint style="info" %}
回文子集：一个string的substring的集合中所有元素都是回文（正反读都是一样的），substring里的字母都不重复
{% endhint %}

![](/files/-M8DTh9yPk946dgcy7YT)

### Solution:

定义一个subs为string类型，相当于子集集合里的每个字符串，每次多加一个字母，判断是否是回文，不是的话继续加一个后面的字母，如果是回文，就加入子集集合中。若是碰到了return就回溯到是回文的状态，尝试别的可能的组合。

**`sub = ''` 非常需要思考放在哪里？遗留问题。**

helper函数的终止条件`if index == len(s)`

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

```python
class Solution:
    def partition(self, s: str) -> List[List[str]]:
        res = []
        self.backtrack(s, 0, [], res)
        return res
        
    def backtrack(self, s, start, level, res):
        # add to res
        if start == len(s):
            res.append(level[:])
            
        for i in range(start+1, len(s)+1):
            subString = s[start:i]
            if self.isPalindrome(subString):
                level.append(subString)
                print(level)
                self.backtrack(s, i, level, res)
                level.pop()
        
    def isPalindrome(self, subString):
        for i in range(len(subString)//2):
            if subString[i] != subString[len(subString) - i -1]:
                return False
            
        return True
```

{% endtab %}

{% tab title="Process" %}

> Input: "aabcd"
>
> Stdout: `[["a","a","b","c","d"],["aa","b","c","d"]]`
>
> Output:`level`(before adding new element), `subs`(may be added to level)

`[] a` 

`['a'] a` 

`['a', 'a'] b` 

`['a', 'a', 'b'] c` 

`['a', 'a', 'b', 'c'] d` 

`['a', 'a', 'b'] cd` 

`['a', 'a'] bc` 

`['a', 'a'] bcd` 

`['a'] ab` 

`['a'] abc` 

`['a'] abcd` 

`[] aa` 

`['aa'] b` 

`['aa', 'b'] c` 

`['aa', 'b', 'c'] d` 

`['aa', 'b'] cd` 

`['aa'] bc` 

`['aa'] bcd` 

`[] aab` 

`[] aabc` 

`[] aabcd`
{% endtab %}

{% tab title="Java(backtrack, O(N\*2^N)" %}

```java
class Solution {
    private List<List<String>> res = new ArrayList<List<String>>();
    
    public List<List<String>> partition(String s) {
        backtrack(s, 0, new ArrayList<String>());
        return res;
    }
    
    private boolean isPalindrome(String s) {
        int i = 0, j = s.length() - 1;
        while(i < j) {
            if(s.charAt(i) != s.charAt(j))
                return false;
            i ++;
            j --;
        }
        return true;
    }
    
    private void backtrack(String s, int start, ArrayList<String> level) {
        if(start == s.length()) {
            res.add(new ArrayList<String>(level));
            return;
        }
        
        for(int end = start + 1; end <= s.length(); end ++) {
            String sub = s.substring(start, end);
                
            if(isPalindrome(sub)) {
                level.add(sub);
                backtrack(s, end, level);
                level.remove(level.size() - 1);
            }
        }
    }
}

// for each element, decide cut or not, so the complexity is 2^n
// for each palindrome, judge it's palindrome or not, takes n
```

{% endtab %}
{% endtabs %}

{% hint style="danger" %}
`string = string[:-1]` is to delete the last element of a string;

`list.pop()` is to delete the last element of a list

can sacrifice space to compute isParlindrome before backtracking, T = O(2^n)
{% endhint %}


---

# 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/iv.-permutations-and-subsets/131.-palindrome-partitioning.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.