LeetCode-131-分割回文串 LeetCode-131-分割回文串

分割回文串

题目描述：给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是回文串。返回 s 所有可能的分割方案。
【LeetCode-131-分割回文串】回文串是正着读和反着读都一样的字符串。
示例说明请见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 result = new ArrayList<>(); public static List partition(String s) { // 如果字符串为null，直接返回空结果集 if (s == null) { return new ArrayList<>(); } // 如果字符串只有一个字符，只可能有一个结果，直接返回 if (s.length() == 1) { List 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 partitions, String curPartition) { // 已经处理到字符串的最后一个字符 if (pos == s.length() - 1) { if (isHuiwen(curPartition)) { // 如果当前分区字符串是回文串，则将当前分区字符串添加到partitions，然后将之添加到结果集中 List 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 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 : partition("aab")) { System.out.println(string); } } }