# 131. Palindrome Partitioning

## LeetCode [**131. Palindrome Partitioning**](https://leetcode-cn.com/problems/palindrome-partitioning/)\*\*\*\*

### Description

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.

### Tags

Backtracking

### Solution

Use the DFS template. Every time we examine the input string from the very first character to the whole string (Note: the index for traversal is from 1 to n, including n) if it is a palindrome. If it is, we append this substring to `path` , then DFS the remaining string. The boundary contiditon is the input string is empty, and we append `path` to the result 2D string slice.

### Complexity

* Time complexity: $$O(n\times2^n)$$, the worst case happens when the input string is the same character repeated n times. Thus it has $$2^n$$ possible partitioning of `s`.
* Space complexity: $$O(n^2)$$, needs $$O(n)$$ for path to store temporary result and stack space $$O(n)$$ for recursion.

### Code

```go
func partition(s string) [][]string {
	var ans [][]string
	dfs(&ans, s, []string{})
	return ans
}

func dfs(ans *[][]string, s string, path []string) {
	if len(s) == 0 {
		temp := make([]string, len(path))
		copy(temp, path)
		*ans = append(*ans, temp)
	}
	for i := 1; i <= len(s); i++ { // note: i is in [1,n]
		if isPalindrome(s[:i]) {
			path = append(path, s[:i])
			dfs(ans, s[i:], path)
			path = path[:len(path)-1]
		}
	}
}

func isPalindrome(s string) bool {
	for i := 0; i < len(s)/2; i++ {
		if s[i] != s[len(s)-i-1] {
			return false
		}
	}
	return true
}
```