关于java:LeetCode131分割回文串

58次阅读

共计 2255 个字符，预计需要花费 6 分钟才能阅读完成。

题目形容：给你一个字符串 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);
        }
    }
}