> For the complete documentation index, see [llms.txt](https://r24zeng.gitbook.io/leetcode-notebook/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](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).

# 131. Palindrome Partitioning

\# Medium

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

![](https://3288217904-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LxJcc9A1TOyn5a5HJQ4%2F-M8Cvv3VBW7VVZt-Oj0p%2F-M8DTh9yPk946dgcy7YT%2FWechatIMG650.png?alt=media\&token=71d4f439-2821-40ee-8404-f6661ee5fe52)

### 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 %}