回溯---分割回文串 Posted on 2021-07-02 00:00:00 2021-07-02 00:00:00 by Author 摘要 字符串又变出花样了,这都能牵扯到递归回溯思想,就就就离谱的一匹!!!!!! # 回溯---分割回文串 1. 题目描述 - 给你一个字符串 `s`,请你将 `s` 分割成一些子串,使每个子串都是 **回文串** 。返回 `s` 所有可能的分割方案。 **回文串** 是正着读和反着读都一样的字符串。 2. 示例描述 - 示例一 - 输入:s = "aab" - 输出:[["a","a","b"],["aa","b"]] - 示例二 - 输入:s = "a" - 输出:[["a"]] 3. 解题思路 - 本题又是一道递归回溯算法,但是本题的难度在于对所给的字符串怎么分割尼,并且在分割的过程中在何时判断分割后的字符串是回文串,首先我们还是按照我自己总结的递归回溯五步法进行梳理逻辑。 - 第一步确定递归的出口条件,很容易分析出来就是把一个字符串分割完,那么每次递归的时候当已经找到该字符串的末尾了,那么本次递归就结束了。第二步就是确定遍历的集合,这个也很好找,就是把所给的字符串分割成一个个字符。字符串分割后的每个字符,就是遍历的集合。第三步就记录本层递归的值,这里处理逻辑有点小复杂,这里就是本题与其他不一样的地方,首先我们要截取字符串,然后判断截取的字符串符合回文串的要求吗??这里我们该怎样截取字符串尼,因为本层遍历递归是在一个循环里,所以我们可以在本层遍历完,也就把本层循环的字符串一小段,一小段的截取出来了,具体截取逻辑Java中带有对字符串截取的函数。接下来就是判断截取的字符串是否满足回文数的要求,这里实现很简单,就是用双指针判断,具体判断逻辑代码中有实现,特别简单。如果截取后的字符串满足回文串的要求,就记录本层本次截取的值,之后就继续执行本层下一层的递归回溯的逻辑,如果截取的字符串不满足回文串的要求,那么说明截取的这一段不行,还得继续往长里截取,直到满足回文串的要求为止,否则本层循环的逻辑都不满题目要求。第四步就是继续执行本层该节点下层的逻辑了,到达这步的前提要求就是截取的字符串满足回文串的要求。第五步就是回退了,因为下层的递归函数已经结束了,到达本层的时候要还原到之前的状态,是为了不影响本层其他集合的递归遍历操作。 - 具体的实现逻辑如下所示,本题实现起来的确有点难度,但是只有递归回溯思想掌握了,那么还是能够实现的。 4. 代码示例 ```java //记录循环遍历的最终结果集 List<List<String>> result = new ArrayList<>(); //记录每次截取的字符串 List<String> re = new ArrayList<>(); public List<List<String>> partition(String s) { //调用自己写的递归回溯算法 trackBacking(0, s, re); return result; } //这个方法实现了判断一个字符串是否为回文串的方式 boolean isCircleNumber(int start, int end, String s) { //用双指针进行判断 for (int i = start, j = end; i < j; i++, j--) { //如果遇到一个字符不满足就返回false if (s.charAt(i) != s.charAt(j)) { return false; } } //如果字符遍历完都符合要求,就返回true return true; } public void trackBacking(int indexStart, String s, List<String> re) { //递归出口的条件判断 if (indexStart >= s.length()) { result.add(new ArrayList<>(re)); return; } //递归回溯的遍历集合 for (int i = indexStart; i < s.length(); i++) { //首先判断截取的字符串是否满足回文串 if (isCircleNumber(indexStart, i, s)) { //满足回文串的要求,就截取满足要求的字符串,记录本次的值 String s1 = s.substring(indexStart, i + 1); re.add(s1); } //如果不满足,就一直找,直到满足回文串的要求的字串 //如果到集合末尾还没有找到,说明本层找不到,就结束本层的递归 //返回到上一层的调用点处 else { continue; } //如果满足回文串要求,就继续执行本层的下一层的递归逻辑 trackBacking(i + 1, s, re); //这里就是回退到本层调用递归函数前的状态,不影响本层遍历其他接的递归逻辑操作 re.remove(re.size() - 1); } } ```
{{ item.content }}
{{ child.content }}