题目内容

给定一个字符串 $s$，需要将其切割为若干连续子串，使得每一段子串都是回文串。请找出并返回所有满足这一要求的分割方案。

约束条件：

• 字符串 $s$ 的长度在 1 到 16 之间。
• $s$ 仅由小写英文字母组成。

输入描述

输入包含一个参数：一个字符串 $s$，表示待分割的原始字符串。

输出描述

返回一个二维列表，其中每个内层列表表示一种分割方案，列表中的字符串按原字符串从左到右的顺序对应切出的各个回文子串。

样例1

输入

b

输出

b

说明

字符串 b 的长度为 1，单个字符本身一定是回文，因此唯一的分割方案就是 [b]，输出为 b。

样例2

输入

ab

输出

a b

说明

字符串 ab 整体不是回文，因为首字符 a 和尾字符 b 不同。因此不能整体作为一段，只能将 a 和 b 分别切开，两个单字符都是回文，所以输出为 a b。

样例3

输入

aa

输出

a a
aa

说明

字符串 aa 整体是回文，所以可以直接切成一段 aa。同时，把两个字符分别切开得到 a 和 a，它们也都是回文。因此共有两种方案，输出中第一行为 a a，第二行为 aa。

样例4

输入

aaa

输出

a a a
a aa
aa a
aaa

说明

字符串 aaa 中的任意连续子串都是回文，所以所有切割位置都可以选择是否切开。全部切开得到 a a a；只在第 1 个字符后切开，剩余 aa 是回文，得到 a aa；只在第 2 个字符后切开，前面 aa 是回文，得到 aa a；完全不切开得到 aaa。因此共有 4 种方案，输出顺序如上。