# LC131 - Palindrome Partitioning

## Problem

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

### Example

**Input:** s = "aab"

**Output:** `[["a","a","b"],["aa","b"]]`

## Solution

Use an array to cache palindromity of substring. Time and space complexity is $$O(n^2)$$.

```python
def partition(self, s: str) -> List[List[str]]:
	arr = [[False] * len(s) for _ in range(len(s))]
	for i in range(len(s)):
		arr[i][i] = True

	for length in range(2, len(s) + 1):	
		for i in range(len(s) - length + 1):
			j = i + length - 1
			if s[i] == s[j]:
				if length == 2 or arr[i + 1][j - 1]:
					arr[i][j] = True
	
	def dfs(start, part):
		if start == len(s):
			res.append(part[:])
			return
	
		for end in range(start, len(s)):
			if arr[start][end]:
	
				dfs(end + 1, part + [s[start:end+1]])
	
	res = []
	dfs(0, [])
	
	return res
```