# 131. Palindrome Partitioning

#### Medium

***

Given a string `s`, partition `s` such that every substring of the partition is a **palindrome**. Return all possible palindrome partitioning of `s`.

A **palindrome** string is a string that reads the same backward as forward.

 

**Example 1:**

```
Input: s = "aab"
Output: [["a","a","b"],["aa","b"]]
```

**Example 2:**

```
Input: s = "a"
Output: [["a"]]
```

 

**Constraints:**

* `1 <= s.length <= 16`
* `s` contains only lowercase English letters.

```python
class Solution:
    def partition(self, s: str) -> List[List[str]]:
        result = []
        self.dfs(s, 0, result, [])
        return result
    
    def dfs(self,string, start= 0, result = [], l = []):
        if start >= len(string):
            result.append(l[:])
        for index in range(start, len(string)):
            if self.plaindrome(string[start:index+1]):
                l.append(string[start:index+1])
                self.dfs(string, index+1, result, l)
                l.pop()

    def plaindrome(self, string):
        return string == string[::-1]
```