【算法训练营Day21】回溯算法part3

分割回文串

题目链接：131. 分割回文串

解题逻辑：

本题的思考方式还是把问题要抽象成一个树形，前文中的组合问题我们大多都是进行递归取数的操作，在本题中变换为了递归切割。我们以“aab”串为例子来构造整个递归的树形结构。

了解了整个递归的大致流程之后，我们从递归三要素来分析这个问题：

• 递归返回值、参数：返回值为void，参数有三个：第一个是要切割的字符串s，第二个是本次要切割的索引devideIndex，第三个是上次切割的索引lastDevideIndex。这样通过第二、三个参数我们就可以确定本次要切割的部分。
• 递归出口：当本次要切割的索引devideIndex超过字符串的长度的时候，收集结果存入结果集
• 递归逻辑：
  • 从当前位置循环往后切割
  • 判断本次切割的部分是否满足回文串，若不满足则跳过该次循环。如何判断回文子串？我们可以在字符串两头初始化双指针，以相同步幅往中间移动，如果直到两指针相遇两指针所指字符全都一样，那么就说明是回文子串
  • 若满足，将本次切割的部分加入到单个收集容器中
  • 递归进行下一次切割
  • 退出递归之后将收集容器的最后一个元素弹出来

代码如下：

class Solution {List<String> item = new ArrayList<>();List<List<String>> result = new ArrayList<>();public List<List<String>> partition(String s) {backtracking(s,1,0);return result;}public void backtracking(String s,int devideIndex,int lastDevideIndex){if(devideIndex > s.length()) {result.add(new ArrayList<String>(item));return;}for(int i = devideIndex;i <= s.length();i++) {StringBuilder word = new StringBuilder(s.substring(lastDevideIndex,i));if (!check(word)) continue;item.add(word.toString());backtracking(s,i + 1,i);item.remove(item.size() - 1);}}private boolean check(StringBuilder sb){for (int i = 0; i < sb.length()/ 2; i++){if (sb.charAt(i) != sb.charAt(sb.length() - 1 - i)){return false;}}return true;}
}

复原IP地址

题目链接：93. 复原 IP 地址

这一题与上一题分割回文串的思路差不多，区别在于本题要固定切四下来确定ip地址的四个部分并且字符串的每一位都要用到。

解题代码如下：

class Solution {List<String> ip = new ArrayList<>();List<String> result = new ArrayList<>();public List<String> restoreIpAddresses(String s) {backtracking(s,1,0);return result;}public void backtracking(String s,int insertIndex,int lastInsertIndex){if(ip.size() == 4) {if(lastInsertIndex != s.length()) return;String temp = String.join(".",ip);result.add(temp);return;}for(int i = insertIndex;i <= s.length();i++) {String part = s.substring(lastInsertIndex,i);if (!isValid(part)) continue;ip.add(part);backtracking(s,i + 1,i);ip.remove(ip.size() - 1);}}public static boolean isValid(String s) {// 检查是否有前导0（长度大于1且以0开头）if (s.length() > 1 && s.charAt(0) == '0') {return false;}// 转换为数字并检查范围try {int num = Integer.parseInt(s);return num >= 0 && num <= 255;} catch (NumberFormatException e) {// 如果转换失败，说明数字太大return false;}}
}

子集

题目链接：78. 子集

解题逻辑：

本题的解题逻辑与前文中的组合问题非常地相似，我们知道组合问题是在N个数里面按一定规则找出k个数的集合。在子集问题中没有k个数的限制，在代码中对应的变化就是收集结果的位置不一样。

代码如下：

class Solution {List<Integer> item = new ArrayList<>();List<List<Integer>> result = new ArrayList<>();public List<List<Integer>> subsets(int[] nums) {backtracking(nums,0);result.add(new ArrayList<Integer>());return result;}public void backtracking(int[] nums,int startIndex){if(item.size() >= nums.length) return;for(int i = startIndex;i < nums.length;i++) {item.add(nums[i]);result.add(new ArrayList<Integer>(item));backtracking(nums,i + 1);item.remove(item.size() - 1);}}
}

子集 II

题目链接：90. 子集 II

解题逻辑：

本题相当于把上道子集与前文中的组合总和II的去重逻辑相结合。直接照搬前面的思想即可。

解题代码：

class Solution {List<Integer> item = new ArrayList<>();List<List<Integer>> result = new ArrayList<>();public List<List<Integer>> subsetsWithDup(int[] nums) {Arrays.sort(nums);backtracking(nums,0);result.add(new ArrayList<Integer>());return result;}public void backtracking(int[] nums,int startIndex){if(item.size() >= nums.length) return;int old = Integer.MIN_VALUE;for(int i = startIndex;i < nums.length;i++) {if(old == nums[i]) continue;item.add(nums[i]);result.add(new ArrayList<Integer>(item));backtracking(nums,i + 1);item.remove(item.size() - 1);old = nums[i];}}
}