# 分割回文串

<p>给你一个字符串 <code>s</code>，请你将<em> </em><code>s</code><em> </em>分割成一些子串，使每个子串都是 <strong>回文串</strong> 。返回 <code>s</code> 所有可能的分割方案。</p>

<p><strong>回文串</strong> 是正着读和反着读都一样的字符串。</p>

<p> </p>

<p><strong>示例 1：</strong></p>

<pre>
<strong>输入：</strong>s = "aab"
<strong>输出：</strong>[["a","a","b"],["aa","b"]]
</pre>

<p><strong>示例 2：</strong></p>

<pre>
<strong>输入：</strong>s = "a"
<strong>输出：</strong>[["a"]]
</pre>

<p> </p>

<p><strong>提示：</strong></p>

<ul>
	<li><code>1 <= s.length <= 16</code></li>
	<li><code>s</code> 仅由小写英文字母组成</li>
</ul>


## template

```java

class Solution {
	public List<List<String>> partition(String s) {
		boolean[][] dp = new boolean[s.length()][s.length()];
		for (int len = 1; len <= s.length(); len++) {
			for (int i = 0; i <= s.length() - len; i++) {
				if (len == 1)
					dp[i][i] = true;
				else if (s.charAt(i) == s.charAt(i + len - 1) && (len == 2 || dp[i + 1][i + len - 2])) {
					dp[i][i + len - 1] = true;
				}
			}
		}
		return solution(s, 0, dp);
	}

	public List<List<String>> solution(String s, int start, boolean[][] dp) {
		ArrayList<List<String>> list = new ArrayList<>();
		if (start == s.length()) {
			List<String> li = new ArrayList<>();
			list.add(li);
			return list;
		}
		for (int i = start; i < s.length(); i++) {
			if (dp[start][i]) {
				String first = s.substring(start, i + 1);
				for (List<String> li : solution(s, i + 1, dp)) {
					li.add(0, first);
					list.add(li);
				}
			}
		}
		return list;
	}

}
```

## 答案

```java

```

## 选项

### A

```java

```

### B

```java

```

### C

```java

```