宰割回文串
题目形容：给你一个字符串
s，请你将s宰割成一些子串，使每个子串都是 回文串 。返回s所有可能的宰割计划。回文串 是正着读和反着读都一样的字符串。
示例阐明请见LeetCode官网。
起源：力扣（LeetCode）
链接：https://leetcode-cn.com/probl...
著作权归领扣网络所有。商业转载请分割官网受权，非商业转载请注明出处。
解法一：递归法
首先解决两种非凡状况，如果字符串为null，间接返回空后果集；如果字符串的长度为1，则只有一种宰割状况，间接返回这种状况。
当字符串的长度大于1时，应用递归的形式解决，其中会应用一个判断字符串是否是回文串的办法isHuiwen，递归过程如下：
- 从字符串的第一个字符开始判断，参数有后面曾经被分区的回文串list、以后地位、以后要判断的子串；
- 首先判断如果曾经解决到字符串的最初一个字符，如果以后分区字符串是回文串，则将以后分区字符串增加到partitions，而后将之增加到后果集中，否则，间接返回；
否则，首先判断以后分区字符串是否是回文串，有两种可能：
- 如果是，则将以后分区字符串增加到partitions，将下一个字符作为新的分区字符串开始递归判断；
- 如果不是，将下一个字符增加到以后分区字符串中，递归判断。
最初，返回后果集。
import java.util.ArrayList;import java.util.Arrays;import java.util.Collections;import java.util.List;public class LeetCode_131 { // 后果集 private static List<List<String>> result = new ArrayList<>(); public static List<List<String>> partition(String s) { // 如果字符串为null，间接返回空后果集 if (s == null) { return new ArrayList<>(); } // 如果字符串只有一个字符，只可能有一个后果，间接返回 if (s.length() == 1) { List<String> partition = new ArrayList<>(); partition.add(s); result.add(partition); return result; } partition(s, 0, new ArrayList<>(), s.substring(0, 1)); return result; } /** * 递归办法 * * @param s 原始字符串 * @param pos 以后地位 * @param partitions 以后地位之前曾经被宰割的回文串 * @param curPartition 以后分区字符串 */ private static void partition(String s, int pos, List<String> partitions, String curPartition) { // 曾经解决到字符串的最初一个字符 if (pos == s.length() - 1) { if (isHuiwen(curPartition)) { // 如果以后分区字符串是回文串，则将以后分区字符串增加到partitions，而后将之增加到后果集中 List<String> newPartitions = new ArrayList<>(Arrays.asList(new String[partitions.size()])); Collections.copy(newPartitions, partitions); newPartitions.add(curPartition); result.add(newPartitions); } return; } // 如果以后分区字符串是回文串，则将以后分区字符串增加到partitions，而后递归判断下一个字符 if (isHuiwen(curPartition)) { List<String> newPartitions = new ArrayList<>(Arrays.asList(new String[partitions.size()])); Collections.copy(newPartitions, partitions); newPartitions.add(curPartition); partition(s, pos + 1, newPartitions, s.substring(pos + 1, pos + 2)); } // 递归解决下一个字符串 partition(s, pos + 1, partitions, curPartition + s.substring(pos + 1, pos + 2)); } /** * 判断字符串是否是回文串 * * @param str 字符串 * @return */ private static boolean isHuiwen(String str) { if (str == null || str.length() < 2) { return true; } for (int i = 0; i < str.length() / 2; i++) { if (str.charAt(i) != str.charAt(str.length() - 1 - i)) { return false; } } return true; } public static void main(String[] args) { for (List<String> string : partition("aab")) { System.out.println(string); } }}【每日寄语】 弃燕雀之小志，慕鸿鹄而高翔。